Prove that up to isomorphism there are exactly two graphs s.t. there at most two vertices with same degree

Question

I've proven the following: For each $n\in\mathbb{N},n\geq 2$ there exists a graph on $n$ vertices such that all degrees are distinct except two. Formally for each $n$ there exists a graph on vertices $v_1,\ldots,v_n$ such that there exists at most one pair $i\neq j$, such that $\deg v_i = \deg v_j$. The construction goes by induction. Either the graph contains a degree $0$ vertex, so the highest degree is $n-2$, and adding a vertex and joining it to everyone else gets the thing done. If it does not contain a degree $0$ vertex, then adding a new vertex and joining it to no one gets the thing done.

I am curious whether this construction leads to a unique graph. More precisely, I would like to show the following:

For each $n\in\mathbb{N}$ there are, up to isomorphism, exactly two graphs on $n$ vertices $v_1,\ldots,v_n$ whose degree sequence satisfies that for at most one pair $i\neq j$ $\deg v_i = \deg v_j$. One of them is disconnected and one of them is connected.

I tried approaching this by induction. The base step for $n=2$ is trivial. There are exactly two graphs on $2$ vertices. Either there is the edge or there isn't. Denote $G_{n,c}$ and $G_{n,d}$ the two graphs for degree $n$. (c - connected, d - disconnected). Assume a graph on $n+1$ vertices satisfying the conditions. Then either it has a vertex of degree $0$, then by removing it I get a graph on $n$ vertices, and using the induction hypothesis, I can say it is isomorphic to $G_{n,c}$ because there was a vertex of degree $n-1$. Similarly, I can argue if there was no vertex of degree $0$, then there was a vertex with degree $n$ so by removing it, I get a graph on $n$ vertices that is isomorphic to $G_{n,d}$ because there's a degree $0$ vertex left. How to argue that this implies "uniqueness" for the $n+1$ vertices?

As a corollary, this would imply that $G_{n,c}$ is complement of $G_{n,d}$ for each $n$.

Answer 1

$G_{n,c}$ and $G_{n,d}$ are effectively two sets of graphs.

What you want to prove is that if $G_{n-1,c}$ and $G_{n-1,d}$ are sets of isomorphic graphs, i.e., sets of graphs such that there is an isomorphism between each pair of graphs in the set, then so are $G_{n,c}$ and $G_{n,d}$. An isomorphism is a bijection $f$ from the vertices of one graph to those of another such that for each pair of vertices $n_1,n_2$, there is an arc from $n_1$ to $n_2$ iff there is one from $f(n_1)$ to $f(n_2)$.

$G_{n,c}$ and $G_{n,d}$ are constructed by extending graphs in $G_{n-1,c}$ and $G_{n-1,d}$ with a node and possibly arcs. You can describe this extension as a mapping $R_n$ that maps each extended graph in $G_{n,c} \cup G_{n,d}$ to the graph in $G_{n-1,c} \cup G_{n-1,d}$ it was extended from.

What you need to prove is that for any two graphs $G_1, G_2$ in $G_{n,c} \cup G_{n,d}$, if $R(G_1) \cong R(G_2)$, then $G_1 \cong G_2$.

For this, it suffices to prove that each isomorphism from $R(G_1)$ to $ R(G_2)$ can be extended to an isomorphism from $G_1$ to $G_2$. The idea of your proof is that this is easy: extend each isomorphism by mapping the new node to the new node; now prove that the extended mapping is an isomorphism by distinguishing three cases: pairs of vertices none of which are new, one of which is new, and both of which are new.

This will prove the graphs you construct are unique up to isomorphism. It doesn't prove the graphs have the desired property (but you already sketch that proof), nor does it prove that no other graphs have the desired property (the exactly in the title) (I think you meant to sketch that, too, it's a pigeonhole argument; but that wasn't obvious to me).