Find all simple graphs with exactly one pair of vertices with the same degree. 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.
 A: 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}.$
A: 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.
