Vertex Condition for Isomorphic Graphs
Theorem
Let $G_1$ and $G_2$ be isomorphic graphs.
Then the degrees of the vertices of $G_1$ are exactly the same as the degrees of the vertices of $G_2$.
Proof
Let $\phi: \map V {G_1} \to \map V {G_2}$ be an isomorphism.
Let $u \in \map V {G_1}$ be an arbitrary vertex of $G_1$ such that $\map \phi u = v \in \map V {G_2}$.
Let $\map {\deg_{G_1} } u = n$.
We need to show that $\map {\deg_{G_2} } v = n$.
As $\map {\deg_{G_1} } u = n$, there exist $u_1, u_2, \ldots, u_n \in \map V {G_1}$ which are adjacent to $u$.
Every other vertex of $G_1$ is not adjacent to $u$.
Let $\map \phi {u_i} = v_i$ for $1, 2, \ldots, n$.
Because $\phi$ is an isomorphism, each of the vertices $v_1, v_2, \ldots, v_n \in \map V {G_2}$ are adjacent to $v$.
Similarly, every other vertex of $G_2$ is not adjacent to $v$.
Thus $\map {\deg_{G_2} } v = n$.
This applies to all vertices $u \in \map V {G_1}$.
Hence the result.
$\blacksquare$
Also see
- Same Degrees of Vertices does not imply Graph Isomorphism: It does not necessarily follow that if the degrees of the vertices of $G_1$ are exactly the same as the degrees of the vertices of $G_2$, then $G_1$ and $G_2$ are isomorphic.
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.2$: Isomorphic Graphs: Theorem $2.4$