Draw All Connected 5-Vertex Graphs with Odd Distances

Assume the usual convention: a graph is simple and undirected, and the distance between two vertices is the length of a shortest path between them. Under these conventions, there is just one graph to draw, up to relabeling: the complete graph on five vertices, $K_5$.

To draw it, place five vertices around a pentagon, draw the five sides, then draw the five diagonals. Those ten edges connect every pair of vertices.

Why the only possible odd distances are 1 and 3

In a connected graph on five vertices, a shortest path never needs to repeat a vertex. It therefore uses at most four edges, so the distance between any two vertices is at most four. If every distance is odd, the only possibilities are consequently 1 and 3.

Suppose two vertices $u$ and $v$ are not adjacent. Their distance cannot be 1, and it must be odd, so it would have to be 3. Take a shortest path between them and write it as

$$u-a-b-v.$$

The vertices $u$ and $b$ are distinct, and there is a path of length 2 from $u$ to $b$ through $a$. Their distance is therefore at most 2. Because every distance between distinct vertices is odd, their distance must be 1. Thus $u$ and $b$ are adjacent.

But then $u-b-v$ is a path of length 2 from $u$ to $v$. That contradicts the assumption that their shortest-path distance is 3. So no two vertices can be nonadjacent. Every pair must be joined by an edge, which is exactly $K_5$.

How to specify the drawing

Label the vertices $1,2,3,4,5$. The edge set is

$$\{12,13,14,15,23,24,25,34,35,45\}.$$

This is a complete description of the drawing: include each of those ten edges. Equivalently, its adjacency matrix has a 0 on the diagonal and a 1 in every off-diagonal position:

$$\begin{pmatrix} 0&1&1&1&1\\ 1&0&1&1&1\\ 1&1&0&1&1\\ 1&1&1&0&1\\ 1&1&1&1&0 \end{pmatrix}.$$

Every two distinct vertices in this graph are adjacent, so their distance is 1, which is odd. This verifies that the graph works, not just that the proof forces it.

Labeled and unlabeled graphs

If the vertices are not assigned fixed names, there is one answer up to isomorphism: $K_5$. If the vertex set is fixed and labeled, there is still only one qualifying edge set: it contains every possible pair of labels. There are $\binom{5}{2}=10$ such pairs.

The word “connected” is satisfied automatically by $K_5$: in fact, every pair has a direct edge. It also ensures that distances are defined and finite in the first place.

Common mistakes

• Including a path or cycle as an answer: A connected graph can have distances of mixed parity. For example, in a path on five vertices, the endpoints are distance 4 apart, which is even.
• Treating distance as any path length: The distance is the shortest path length. Extra detours do not change it.
• Assuming the result for every graph order: The key bound here is that a graph on five vertices has distances at most four. The argument above uses that bound to reduce the possibilities to 1 and 3.