Find all simple graphs with exactly one pair of vertices with the same degree.

Question

A simple graph is one with no loops or double edges.

A classical Graph theory result is that all graphs have at least one pair of vertices with the same degree. I am wondering which graphs have only one pair.

Give a characterization if possible. If not possible, prove that it is impossible.

Answer 1

For $n > 1,$ there are precisely two such graphs that are the complement of each other and one of them is disconnected. The graph of order $n$ is obtained by taking $G_2 = K_2$ and for $G_{n+1} = \overline{G_{n}} * K_1.$

To see that the claim holds observe that for $n = 2$ the claim is obviously true. Suppose now that $G,\overline{G}$ are two graphs of order $n$ having precisely two vertices of the same degree, and that $G$ is disconnected. Then you can create two such graphs of order $n+1$ by adding a vertex to $G$ and joining it to all vertices of $G,$ and similarly you can create a graph from $\overline{G}$ simply by adding a vertex of degree $0.$

Conversely if $G'$ is a graph of order $n+1$ having precisely two vertices of the same degree then by removing the vertex of degree $n$ or $0$ one (by induction) again obtains either $G$ or $\overline{G}.$

Answer 2

First of all, it is almost trivial to prove that the degrees cannot be pairwise different :

If n vertices would have the degrees $0,1,...,n-1$, there would be a vertex connected with every other vertex, which contradicts the fact that there is some isolated vertex.

The possible sequences for $n = 2$ to $7$ are :

$n=2$

$00,11$

$n=3$

$011,112$

$n=4$

$0112,1223$

$n=5$

$01223,12234$

$n=6$

$012234,123345$

The number appearing twice in the sequence with the $0$ is $[\frac{n-1}{2}]$. In the first sequence, the vertex $n-1$ is missing , in the second, it is the vertex $0$. Coinciding with jernej's claim, the second sequence is the complement of the first.