Definition:Isomorphism (Graph Theory)

This page is about isomorphisms in graph theory. For other uses, see Definition:Isomorphism.

Definition

Let $G = \left({V \left({G}\right), E \left({G}\right)}\right)$ and $H = \left({V \left({H}\right), E \left({H}\right)}\right)$ be graphs.

Let there exist a bijection $F: V \left({G}\right) \to V \left({H}\right)$ such that for each edge $\left\{{u, v}\right\} \in E \left({G}\right)$, there is an edge $\left\{{F \left({u}\right), F \left({v}\right)}\right\} \in E \left({H}\right)$.

That is, that:

• $F: V \left({G}\right) \to V \left({H}\right)$ is a homomorphism, and

• $F^{-1}: V \left({H}\right) \to V \left({G}\right)$ is a homomorphism.

Then $G$ and $H$ are isomorphic, and this is denoted $G \cong H$.

The function $F$ is called an isomorphism from $G$ to $H$.

It follows from this definition that Graph Isomorphism is an Equivalence.

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 2.2$