Isomorphisms and Subgraphs

🔗

Section 5.4 Isomorphisms and Subgraphs

🔗

Objectives

Define graph isomorphism and distinguish it from graph equality.
Define subgraphs and the complement of a graph. Find subgraphs of a given type in a graph; construct the complement of a graph.
Determine whether or not two graphs are isomorphic; if they are, deductively construct an adjacency-preserving bijection between their vertex sets.
Prove statements about graph structure in relation to the concepts in this chapter.

🔗

Video: Isomorphisms

🔗

Given any graph

G = (V, E),

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} ?

🔗

Example 5.4.1. Are These the Same Graphs?

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} ≅ G_{2},$ if there exists a function

f : V_{1} \to V_{2}

such that for all $u, v \in V_{1},$

(u, v) \in E (G_{1}) \Leftrightarrow (f (u), f (v)) \in E (G_{2}) .

That is, $f$ preserves adjacencies between vertices.

We call $f$ an isomorphism from $G_{1}$ to $G_{2};$ we also say $G_{1}$ is isomorphic to $G_{2} .$

🔗

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.)

🔗

Checkpoint 5.4.4. Verify and Construct Isomorphisms.

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!)

🔗

Checkpoint 5.4.5. Which Pairs are Isomorphic?

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.

🔗

Proposition 5.4.6. Isomorphic Graphs have the Same Number of Edges.

If $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ are isomorphic simple graphs, prove that they must have the same number of edges, or $| E_{1} | = | E_{2} | .$

🔗

Proof.

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{.}$

🔗

Checkpoint 5.4.7. Isomorphic Graphs have the Same Degree Sequence.

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

🔗

Checkpoint 5.4.8. Check Degree Sequences.

Use Checkpoint 5.4.7 to determine which pairs in Checkpoint 5.4.5 are not isomorphic.

🔗

Checkpoint 5.4.9. Same Degree Sequence does not imply Isomorphism.

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),$ a subgraph of $G$ is another graph $G^{'} = (V^{'}, E^{'})$ where

$V^{'} \subseteq V$
$E^{'} \subseteq E$
$(v_{1}, v_{2}) \in E^{'} \Rightarrow v_{1}, v_{2} \in V^{'} .$

🔗

Example 5.4.11. Subgraph Example.

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{.}$

🔗

Example 5.4.12. Subgraphs for Non-isomorphism.

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.

🔗

Example 5.4.13. Prove Graph Isomorphism.

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$

🔗

Checkpoint 5.4.14. Prove Graph Isomorphism.

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 $\overset{―}{G}$ to be the graph on the same vertex set $V (G),$ and with edge set

E^{'} = {(u, v) \in V \times V : (u, v) \notin E},

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

🔗

Example 5.4.16. A Graph and its Complement.

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

🔗

Proposition 5.4.17. Complements are Isomorphic.

Two graphs $G$ and $H$ are isomorphic if and only if their complements $\overset{―}{G}$ and $\overset{―}{H}$ are.

🔗

Checkpoint 5.4.18. Verify Proposition 5.4.17.

Verify Proposition 5.4.17 on Example 5.4.13 and Checkpoint 5.4.14.

🔗

Checkpoint 5.4.19. Prove Proposition 5.4.17.

Prove Proposition 5.4.17.

🔗

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.

\(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\)