Vertex Condition for Isomorphic Graphs

From ProofWiki
Jump to navigation Jump to search

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: V \left({G_1}\right) \to V \left({G_2}\right)$ be an isomorphism.

Let $u \in V \left({G_1}\right)$ be an arbitrary vertex of $G_1$ such that $\phi \left({u}\right) = v \in V \left({G_2}\right)$.

Let $\deg_{G_1} \left({u}\right) = n$.

We need to show that $\deg_{G_2} \left({v}\right) = n$.


As $\deg_{G_1} \left({u}\right) = n$, there exist $u_1, u_2, \ldots, u_n \in V \left({G_1}\right)$ which are adjacent to $u$.

Every other vertex of $G_1$ is not adjacent to $u$.

Let $\phi \left({u_i}\right) = v_i$ for $1, 2, \ldots, n$.

Because $\phi$ is an isomorphism, each of the vertices $v_1, v_2, \ldots, v_n \in V \left({G_2}\right)$ are adjacent to $v$.

Similarly, every other vertex of $G_2$ is not adjacent to $v$.

Thus $\deg_{G_2} \left({v}\right) = n$.

This applies to all vertices $u \in V \left({G_1}\right)$.

Hence the result.

$\blacksquare$


Note

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