Prove there is a unique connected simple graph with degree sequence $2,2,\dots,2,1,1$.

Question

My attempt: Assume that graph is connected, that unique graph is basically a "line" with vertices on it. The vertices with degree $1$ and these vertices can only be on the two ends, and vertices with degree $2$ are in the middle. Am I correct? Is there a formal way to present it?

Answer 1

The formal notion of "equality" between graphs is isomorphism. Technically, you can have different graphs with that degree sequence: the first graph can have vertex set $\{1, 2, 3, \dots n\}$, while the the other can have vertex set $\{A, B, C, \dots, Z\}$. What's important is, we can prove that they are isomorphic.

Assume there are two graphs, $G(V, E)$ and $G^\prime(V^\prime, E^\prime)$, both with degree sequence $2, 2, \dots, 2, 1, 1$. We will construct a function $f: V \to V^\prime$ such, that $(v_1, v_2) \in V \iff (f(v_1), f(v_2)) \in V^\prime$. The existence of such function proves the isomorphism.

Let $n = |V| = |V^\prime|$, and let $v_1$ and $v_n$ be the 1-degree vertices of $G$. There exists a path $v_1, v_2, v_3, \dots, v_n$ between $v_1$ and $v_n$ (G is connected). Assume vertex $u$ is not in the path. $v_1$ and $v_n$ have degree 1, and each have a neighbor in the path. $v_i$ for $i \neq 1, n$ has degree 2 and has 2 neighbors in the path. Therefore, there is no edge connecting vertices in the path with a vertex outside the path, which breaks the connectivity condition. So all vertices are in the path, and its length is $n$.

Similarly, we can construct a path of length $n$, $v_1^\prime, v_2^\prime, \dots v_n^\prime$ of length $n$ between the 1-degree vertices in $G^\prime$, and it will ocntain all vertices in $V^\prime$.

Let $f(v_i) = v_i^\prime$. The neighbors of $v_i$ and $v_{i-1}$ and $v_{i+1}$ (or only one if $i \in \{1, n\}$, and the neighbors of $f_{v_i} = v_i^\prime$ are exactly $v_{i-1}^\prime = f(v_{i-1})$ and $v_{i+1}^\prime = f(v_{i+1})$, as desired.