Skip to main content

Section 5.4 Isomorphisms and Subgraphs

Video: Isomorphisms

Given any graph \(G = (V,E)\text{,}\) there is usually more than one way of representing \(G\) as a drawing. In fact, the definition of a graph (Definition 5.2.1) as a pair \((V,E)\) of vertex and edge sets makes no reference to how it is visualized as a drawing on a sheet of paper. So when we say ‘consider the following graph’ when referring to a drawing, we technically mean: ‘consider the graph that is represented by this drawing…’

In the next example it is clear that \(G_2\) and \(G_3\) are exactly the same graph. But how about \(G_1\text{?}\)

Let \(G_1\text{,}\) \(G_2\text{,}\) and \(G_3\) be the following graphs:

Clearly \(G_2\) and \(G_3\) are equal as graphs—their vertex sets

\begin{equation*} V = \{v_1,v_2,v_3,v_4,v_5\} \end{equation*}

and edge sets

\begin{equation*} E = \{(v_1,v_2),(v_2,v_3),(v_3,v_4),(v_4,v_5),(v_5,v_1)\} \end{equation*}

are exactly the same, even if they are drawn differently on the plane.

As for \(G_1\text{,}\) it is apparent that it has the same structure as both \(G_2\) and \(G_3\text{:}\) they are all the cycle graph on five vertices, or \(C_5\text{,}\) even if they don't share the same vertex set (\(V(G_1) = \{a,b,c,d,e\}\)). This motivates our next definitions.

Definition 5.4.2. Graph Equality.

Two graphs \(G_1 = (V_1,E_1)\) and \(G_2 = (V_2,E_2)\) are said to be equal if and only if both \(V_1 = V_2\) and \(E_1 = E_2\) hold.

Definition 5.4.3. Graph Isomorphism.

Two simple graphs \(G_1 = (V_1,E_1)\) and \(G_2 = (V_2,E_2)\) are said to be isomorphic, denoted by \(G_1 \cong G_2\text{,}\) if there exists a function

\begin{equation*} f: V_1 \rightarrow V_2 \end{equation*}

such that for all \(u, v \in V_1\text{,}\)

\begin{equation*} (u,v) \in E(G_1) \Leftrightarrow (f(u),f(v)) \in E(G_2)\text{.} \end{equation*}

That is, \(f\) preserves adjacencies between vertices.

We call \(f\) an isomorphism from \(G_1\) to \(G_2\text{;}\) we also say \(G_1\) is isomorphic to \(G_2\text{.}\)

When two graphs \(G_1\) and \(G_2\) are isomorphic, this means one can relabel the vertices of \(G_2\) to match the vertex names of \(G_1\) such that both graphs become equal. (Note that we only define isomorphisms for simple graphs at the moment.)

Verify that in the graphs of Example 5.4.1, the function \(f: V(G_1) \rightarrow V(G_2)\) given by

\begin{equation*} f(a) = v_1, f(b) = v_5, f(c) = v_4, f(d) = v_3, f(e) = v_2 \end{equation*}

is an isomorphism.

Then, construct two other isomorphisms from \(G_1\) to \(G_2\text{.}\) (Yes, there can be multiple!)

Given the graphs \(H_1\text{,}\) \(H_2\text{,}\) \(H_3\text{,}\) and \(H_4\text{,}\) which pairs (if any) are isomorphic?

\(H_2 = (V_2,E_2)\text{,}\) where \(V_2 = \{v_1,v_2,v_3,v_4,v_5\}\) and \(E_2 = \{(v_1,v_2),(v_3,v_4),(v_4,v_5),(v_5,v_3)\}\text{.}\)

\(H_3 = (V_3,E_3)\text{,}\) where \(V_3 = \{p,q,r,s,t\}\) and \(E_3 = \{(p,q),(p,r),(p,s),(p,t),(r,t),(s,q)\}\)

It is typically easier to prove that two graphs are not isomorphic, than to prove that they are, since two isomorphic graphs must agree on many of their structural properties. Most obviously, two isomorphic graphs must have the same number of vertices—this is an immediate consequence of the fact that the function \(f\) defining the isomorphism is a bijection.

We now prove two isomorphic graphs must have the same number of edges as well.

Let \(f: V_1 \rightarrow V_2\) be an isomorphism from \(G_1\) to \(G_2\text{.}\) To prove \(|E_1| = |E_2|\) we construct a bijection between these two sets.

We know from Definition 5.4.3 that for any pair of vertices \(u,v \in V_1\text{,}\)

\begin{equation*} (u,v) \in E_1 \Leftrightarrow (f(u),f(v)) \in E_2\text{.} \end{equation*}

So define a function \(g: E_1 \rightarrow E_2\) such that \(g\left( (u,v) \right) = \left( f(u),f(v)\right)\text{.}\)

Since \(f\) is injective, \(g\) must also be injective. Also \(g\) must be surjective since any edge \((x,y) \in E_2\) has a preimage \((f^{-1}(x),f^{-1}(y))\) in \(E_1\text{.}\) Thus \(g\) is a bijection, and \(|E_1| = |E_2|\text{.}\)

Prove that two isomorphic simple graphs must have the same degree sequence.

The converse of Checkpoint 5.4.7 is not true. Find a counterexample, i.e. two non-isomorphic graphs with the same degree sequence.

Hint

2, 2, 2, 1, 1

Another way we can prove two graphs are not isomorphic is by looking at their subgraphs, which are graphs whose vertices and edges are subsets of that of the original graph.

Video: Subgraphs and Complements

Definition 5.4.10. Subgraph.

Given a graph \(G = (V,E)\text{,}\) a subgraph of \(G\) is another graph \(G' = (V', E')\) where

  • \(\displaystyle V' \subseteq V\)
  • \(\displaystyle E' \subseteq E\)
  • \((v_1,v_2) \in E' \Rightarrow v_1,v_2 \in V'\text{.}\)

Suppose we label the vertices of \(K_4\) to be \(V = \{1,2,3,4\}\text{,}\) so that its edges are \(E = \{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\}\text{.}\)

The cycle graph \(C_4\) arises as a subgraph of the complete graph \(K_4\text{,}\) by taking \(V' = \{1,2,3,4\}\) and \(E' = \{(1,2),(2,3),(3,4),(1,4)\}\text{.}\)

The graphs \(H_1\) and \(H_2\) have the same degree sequence 4, 4, 4, 4, 4, 4, 4, 4 so we cannot use this to rule out isomorphism. However, \(H_2\) has a \(K_4\) subgraph, while \(H_1\) does not, which tells us that they are not isomorphic.

The reason why this is sufficient to conclude they are not isomorphic is that no matter how we try to form the bijection \(f: V(H_1) \rightarrow V(H_2)\text{,}\) we will never be able to find four vertices in \(V(H_1)\) to map to \(\{1,2,3,4\}\) in \(V(H_2)\) that also preserve adjacency relations. That is, no four vertices in \(H_1\) are all connected to one another by edges, as opposed to \(\{1,2,3,4\}\text{,}\) which are all adjacent to one another in \(H_2\text{.}\)

In the next example we explicitly construct an adjacency-preserving bijection between the vertex sets of two graphs that are isomorphic.

The following graphs are isomorphic. To produce the bijection \(f\) explicitly we examine the degrees and adjacencies of the vertices.

The degree sequence of both graphs is 4, 4, 4, 3, 3, 2. So the vertex with degree 2 in \(G\) must be mapped to the vertex with degree 2 in \(H\text{;}\) this means \(3 \leftrightarrow t\) in any isomorphism.

There are two vertices of degree 3 in each: \(\{2,5\}\) in \(G\) and \(\{q,r\}\) in \(H\text{.}\) So we should map either

\begin{equation*} 2 \leftrightarrow q \text{ and } 5 \leftrightarrow r, \quad \text{or} \quad 2 \leftrightarrow r \text{ and } 5 \leftrightarrow q\text{.} \end{equation*}

Clearly it must be the first option, since \(2\) is adjacent to \(3\) (the vertex with degree 2) in \(G\text{,}\) while \(q\) is adjacent to \(t\) in \(H\text{.}\)

Now we just need to determine how the four vertices of degree 4 \(\{1, 4, 6\}\) in \(G\) are mapped to those in \(H\text{,}\) \(\{p, s, u\}\text{.}\) Observe that we must have \(4 \leftrightarrow p\text{,}\) since they are both adjacent to the vertex of degree 2 in their graphs.

As for the others, you can check that both ways of assigning \(\{s,u\}\) to \(\{1,6\}\) will produce an isomorphism. So we see there are two isomorphisms between \(G\) and \(H\text{:}\)

\(G\) \(3\) \(2\) \(5\) \(4\) \(1\) \(6\)
\(H\) \(t\) \(q\) \(r\) \(p\) \(s\) \(u\)
\(G\) \(3\) \(2\) \(5\) \(4\) \(1\) \(6\)
\(H\) \(t\) \(q\) \(r\) \(p\) \(u\) \(s\)

Prove the following graphs are isomorphic:

Sometimes when graphs have many edges, it is easier to look at the edges they don't have!

Definition 5.4.15. Graph Complement.

Let \(G = (V,E)\) be a simple graph. We define its complement \(\overline{G}\) to be the graph on the same vertex set \(V(G)\text{,}\) and with edge set

\begin{equation*} E' = \{(u,v) \in V \times V: (u,v) \not\in E\}\text{,} \end{equation*}

that is, \((u,v)\) is an edge in \(\overline{G}\) if and only if it was not an edge in \(G\text{.}\)

A graph \(G\) (red) and its complement \(\overline{G}\) (blue) are shown below.

Remark 5.4.20.

In general it is a difficult problem to determine whether or not two graphs are isomorphic. While algorithms exist that work well on random graphs, in the worst-case some of these still exhibit exponential-time behaviour. For some special cases this problem has efficient solutions that run in polynomial time. See this page and the references therein to read more about the problem.