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$.

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$

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.

1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.2$: Isomorphic Graphs: Theorem $2.4$