11.4: Graph Isomorphisms

Last updated
Save as PDF

Page ID: 60130

Joy Morris
University of Lethbridge

$ \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}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

There is a problem with the way we have defined $K_n$. A graph is supposed to consist of two sets, $V$ and $E$. Unless the elements of the sets are labeled, we cannot distinguish amongst them. Here are two graphs, $G$ and $H$:

$clipboard_e12f78e2e42f3751f71037f10f8451ee9.png$

Which of these graphs is $K_2$? They can’t both be $K_2$ since they aren’t the same graph – can they?

The answer lies in the concept of isomorphisms. Intuitively, graphs are isomorphic if they are identical except for the labels (on the vertices). Recall that as shown in Figure 11.2.3, since graphs are defined by the sets of vertices and edges rather than by the diagrams, two isomorphic graphs might be drawn so as to look quite different.

Definition: Isomorphism

Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic if there is a bijection (a one-to-one, onto map) $\varphi$ from $V_1$ to $V_2$ such that

\[\{v, w\} ∈ E_1 ⇔ \{\varphi(v), \varphi(w)\} ∈ E_2.\]

In this case, we call $\varphi$ an isomorphism from $G_1$ to $G_2$.

Notation

When $\varphi$ is an isomorphism from $G_1$ to $G_2$, we abuse notation by writing $\varphi: G_1 → G_2$ even though $\varphi$ is actually a map on the vertex sets.

We also write $G_1 \cong G_2$ for “$G_1$ is isomorphic to $G_2$.”

So a graph isomorphism is a bijection that preserves edges and non-edges. If you have seen isomorphisms of other mathematical structures in other courses, they would have been bijections that preserved some important property or properties of the structures they were mapping. For graphs, the important property is which vertices are connected to each other. If that is preserved, then the networks being represented are for all intents and purposes, the same.

Recall from $\text{Math } 2000$, a relation is called an equivalence relation if it is a relation that satisfies three properties. It must be:

reflexive (every object must be related to itself);
symmetric (if object $A$ is related to object $B$, then object $B$ must also be related to object $A$); and
transitive (if object $A$ is related to object $B$ and object $B$ is related to object $C$, then object $A$ must be related to object $C$).

The relation “is isomorphic to” is an equivalence relation on graphs. To see this, observe that:

For any graph $G$, we have $G \cong G$ by the identity map on the vertices;
For any graphs $G_1$ and $G_2$, we have

\[G_1 \cong G_2 ⇔ G_2 \cong G_1,\]

since any bijection has an inverse function that is also a bijection, and since

\[\{v, w\} ∈ E_1 ⇔ \{\varphi(v), \varphi(w)\} ∈ E_2\]

is equivalent to

\[{\varphi^{−1} (v), \varphi^{−1} (w)} ∈ E_1 ⇔ \{v, w\} ∈ E_2;\]

For any graphs $G_1$, $G_2$, and $G_3$ with $\varphi_1 : G_1 → G_2$ and $\varphi_2 : G_2 → G_3$ being isomorphisms, the composition $\varphi_2 ◦ \varphi_1 : G_1 → G_3$ is a bijection, and

\[\{v, w\} ∈ E_1 ⇔ \{\varphi_1(v), \varphi_1(w)\} ∈ E_2 ⇔ \{\varphi_2(\varphi_1(v)), \varphi_2(\varphi_1(w))\} ∈ E_3,\]

so $G_1 \cong G_3$.

The answer to our question about complete graphs is that any two complete graphs on $n$ vertices are isomorphic, so even though technically the set of all complete graphs on $2$ vertices is an equivalence class of the set of all graphs, we can ignore the labels and give the name $K_2$ to all of the graphs in this class.

Example $\PageIndex{1}$

The graphs $G$ and $H$:

$clipboard_e26629211896e31c00ab2bc8f8d620587.png$

are isomorphic. The map $\varphi$ defined by

$\varphi(a) = v$;
$\varphi(b) = z$;
$\varphi(c) = y$;
$\varphi(d) = x$;
$\varphi(e) = w$

To prove that two graphs are isomorphic, we must find a bijection that acts as an isomorphism between them. If we want to prove that two graphs are not isomorphic, we must show that no bijection can act as an isomorphism between them.

Sometimes it can be very difficult to determine whether or not two graphs are isomorphic. It is possible to create very large graphs that are very similar in many respects, yet are not isomorphic. A common approach to this problem has been attempting to find an “invariant” that will distinguish between non-isomorphic graphs. An “invariant” is a graph property that remains the same for all graphs in any isomorphism class. Thus, if you can find an invariant that is different for two graphs, you know that these graphs must not be isomorphic. We say in this case that this invariant distinguishes between these two graphs.

Mathematicians have come up with many, many graph invariants. Unfortunately, so far, for every known invariant it is possible to find two graphs that are not isomorphic, but for which the invariant is the same. In other words, no known invariant distinguishes between every pair of non-isomorphic graphs.

As an aside for those of you who may know what this means (probably those in computer science), the graph isomorphism is particularly interesting because it is one of a very few (possibly two, the other being integer factorisation) problems that are known to be in NP but that are not known to be either in P, or to be NP-complete.

We give a few graph invariants in the following proposition.

Proposition $\PageIndex{1}$

If $G_1 \cong G_2$ are graphs, then

$G_1$ and $G_2$ have the same number of vertices;
$G_1$ and $G_2$ have the same number of edges;
if we list the valency of every vertex of $G_1$ and do the same for $G_2$, the lists will be the same (though possibly in a different order). (Such a list is called the degree sequence of the graph.)

Proof

Since $G_1 \cong G_2$, there is an isomorphism $\varphi : V_1 → V_2$ (where $V_1$ is the vertex set of $G_1$ and $V_2$ is the vertex set of $G_2$). Since $\varphi$ is a bijection, we must have $|V_1| = |V_2|$.
Since \[\{v, w\} ∈ E_1 ⇒ \{\varphi(v), \varphi(w)\} ∈ E_2,\] we see that for every edge of $E_1$, there is an edge of $E_2$. Therefore, $|E_2| ≥ |E_1|$. Similarly, since \[\{\varphi(v), \varphi(w)\} ∈ E_2 ⇒ \{v, w\} ∈ E_1,\] we see that $|E_1| ≥ |E_2|$. So $|E_1| = |E_2|$.
If $\varphi(v_1) = v_2$ then $d_{G_1} (v_1) = d_{G_2} (v_2)$, because $u ∼ v_1$ if and only if $\varphi(u) ∼ v_2$.

Example $\PageIndex{2}$

The graph $G$ of Example 11.4.1 is not isomorphic to $K_5$, because $K_5$ has $\binom{5}{2} = 10$ edges by Proposition 11.3.1, but $G$ has only $5$ edges. Notice that the number of vertices, despite being a graph invariant, does not distinguish these two graphs

The graphs $G$ and $H$:

$clipboard_e2cabbd6f7bf529447320b27905dd7483.png$

are not isomorphic. Each of them has $6$ vertices and $9$ edges. However, the graph $G$ has two vertices of valency $2$ ($a$ and $c$), two vertices of valency $3$ ($d$ and $e$), and two vertices of valency $4$ ($b$ and $f$). Meanwhile, the graph $H$ has one vertex of valency $2$ ($w$), four vertices of valency $3$ ($u$, $x$, $y$, and $z$), and one vertex of valency $4$ ($v$). Although each of these lists has the same values ($2$s, $3$s, and $4$s), the lists are not the same since the number of entries that contain each of the values is different. In particular, the two vertices $a$ and $c$ both have valency $2$, but there is only one vertex of $H$ (vertex $w$) of valency two. Either $a$ or $c$ could be sent to $w$ by an isomorphism, but either choice leaves no possible image for the other vertex of valency $2$. Therefore, an isomorphism between these graphs is not possible.

Observe that the two graph

$clipboard_e5a44714e0bc9bd2ef60cda94142c303d.png$

both have $6$ vertices and $7$ edges, and each has four vertices of valency $2$ and two vertices of valency $3$. Nonetheless, these graphs are not isomorphic. Perhaps you can think of another graph invariant that is not the same for these two graphs.

To prove that these graphs are not isomorphic, since each has two vertices of valency $3$, any isomorphism would have to map $\{c, f\}$ to $\{v, z\}$. Now, whichever vertex gets mapped to $u$ must be a mutual neighbour of $c$ and $f$ since $u$ is a mutual neighbour of $v$ and $z$. But $c$ and have no mutual neighbours, so this is not possible. Therefore there is no isomorphism between these graphs.

A natural problem to consider is: how many different graphs are there on $n$ vertices? If we are not worrying about whether or not the graphs are isomorphic, we could have infinitely many graphs just by changing the labels on the vertices, and that’s not very interesting. To avoid this problem, we fix the set of labels that we use. Label the vertices with the elements of $\{1, . . . , n\}$. We’ll call the number of graphs we find, the number of labeled graphs on $n$ vertices.

Any edge is a $2$-subset of $\{1, . . . , n\}$. There are $\binom{n}{2}$ possible edges in total. Any graph is formed by taking a subset of the $\dfrac{n(n − 1)}{2}$ possible edges. In Example 4.1.1, we learned how to count these: there are $\dfrac{2n(n−1)}{2}$ subsets

Example $\PageIndex{3}$

When $n = 1$, we have $\binom{1}{2} = 0$, and $2^0= 1$, so there is exactly one labeled graph on $1$ vertex. It looks like this:

$clipboard_eb99a858cf7a1c8a30530820931147f9f.png$

When $n = 2$, we have $\binom{2}{2} = 1$, and $2^1 = 2$. so there are exactly two labeled graphs on $2$ vertices. They look like this:

$clipboard_e9f05fad25bc025fcb80a512bcbaf8914.png$

When $n = 3$, we have $\binom{3}{2} = 3$, and $2^3 = 8$, so there are exactly eight labeled graphs on $3$ vertices. They look like this:

$clipboard_e8973f7b9ae644505ed2af6acb6d2b3e6.png$

When $n = 4$, we have $\binom{4}{2} = 6$, and $2^6 = 64$, so there are exactly sixty-four labeled graphs on $4$ vertices. We won’t attempt to draw them all here.

Although that answer is true as far as it goes, you will no doubt observe that even though we are using a fixed set of labels, some of the graphs we’ve counted are isomorphic to others. A more interesting question would be, how many isomorphism classes of graphs are there on $n$ vertices? Since we are considering isomorphism classes, the labels we choose for the vertices are largely irrelevant except to tell us which vertices are connected to which other vertices, if we don’t have a diagram. Thus, if we are drawing the graphs, we usually omit vertex labels and refer to the resulting graphs (each of which represents an isomorphism class) as unlabeled. So the question is, how many unlabeled graphs are there on $n$ vertices?

We can work out the answer to this for small values of $n$. From the labeled graphs on $3$ vertices, you can see that there are four unlabeled graphs on $3$ vertices. These are:

$clipboard_e3cdad5cd93b65564a28c2e1dfc673c54.png$

There are $11$ unlabeled graphs on four vertices. Unfortunately, since there is no known polynomial-time algorithm for solving the graph isomorphism problem, determining the number of unlabeled graphs on $n$ vertices gets very hard as $n$ gets large, and no general formula is known.

Exercise $\PageIndex{1}$

For each of the following pairs of graphs, find an isomorphism or prove that the graphs are not isomorphic.

1) $clipboard_e8f809d3a59ece3f8496df2d53327cb48.png$

2) $clipboard_ef1fa1fd4749d3261dc9576a38d51f3f1.png$

3) $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ with $V_1 = \{a, b, c, d\}$, $V_2 = \{A, B, C, D\}$, $E_1 = \{ab, ac, ad\}$, $E_2 = \{BC, CD, BD\}$.

Exercise $\PageIndex{2}$

Draw five unlabeled graphs on $5$ vertices that are not isomorphic to each other.
How many labeled graphs on $5$ vertices have $1$ edge?
How many labeled graphs on $5$ vertices have $3$ or $4$ edges

Search

Text Color

Text Size

Margin Size

Font Type