5.3: Graph Isomorphism

Last updated
Save as PDF

Page ID: 88870

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

When calculating properties of the graphs in Figure 5.2.43 and Figure 5.2.44, you may have noted that some of the graphs shared many properties. It should also be apparent that a given graph can be drawn in many different ways given that the relative location of vertices and shape of edges is irrelevant. If two graphs are essentially the same, they are called isomorphic.

Definition \(\PageIndex{1}\): Graph Isomorphism.

Two graphs \(G=(V_G,E_G)\) and \(H=(V_H,E_H)\) are isomorphic if and only if there exists a Bijection, called the isomorphism, \(f:V_G \to V_H\) such that \(\{v_1,v_2\} \in E_G\) if and only if \(\{f(v_1),f(v_2)\} \in E_H.\)

Example \(\PageIndex{2}\): Isomorphic Graphs.

The two graphs in Figure \(\PageIndex{3}\) are isomorphic. The isomorphism is

\begin{align*} A \mapsto & I\\ B \mapsto & J\\ C \mapsto & L\\ D \mapsto & K\\ E \mapsto & M\\ F \mapsto & N\\ G \mapsto & P\\ H \mapsto & O \end{align*}

Drag the vertices of the graph on the left around until that graph looks like the graph on the right.

Figure \(\PageIndex{3}\) Two Isomorphic Graphs

Checkpoint \(\PageIndex{4}\)

Determine which graphs in Figure 5.2.43 and Figure 5.2.44 are isomorphic. State the isomorphism (i.e., explicitly give the function).