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?

  • 1
    $\begingroup$ But the statement in the title of your question is false, because the graph is not unique without assuming connectedness. Or was the original question about connected graphs, and you accidentally omitted the word "connected" from the title? $\endgroup$ – bof Nov 20 '18 at 3:32
  • $\begingroup$ @bof Yes it's assumed to be connected. I should've been more clear $\endgroup$ – Thomas Nov 20 '18 at 15:58

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.