Graph Isomorphisms

We first look at the definition of what an isomorphism between two graphs $G$ and $H$:

Definition: For two graphs $G = (V(G), E(G))$, and $H = (V(H), E(H))$ the graph $G$ is an isomorphism of $H$ if there exists a bijection such that $f: V(G) \rightarrow V(H)$ so that $\left\{ {x, y}\right\} \in E(G)$ if and only if $\left\{ {f(x), f(y)}\right\} \in E(H)$. If this is the case, we say that there exists an Isomorphism from graph $G$ to graph $H$, denoted such that $G \cong H$.

While this definition may look confusing, it essentially says that there exists a function $f$, such that for every pair of vertices $\{x, y \}$ forming an edge in the edge set $E(G)$, then the pair of vertices transformed by the function $f$, or the image pair $\{ f(x), f(y) \}$ forms an edge in the edge set $E(H)$. If this occurs for all pairs $\{ x, y \}$ and also for all occurrences where the pair $\{ x, y \}$ does not form an edge in $E(G)$, then the graph $G$ is said to be isomorphic to the graph $H$.

For example, let's look at the following two graphs $G$ and $H$:

The first step to determine if two graphs are isomorphic is to check to see if the number of vertices in graph $G$ is equal to the number of vertices in $H$, or:

(1)

\begin{align} \quad \mid V_G(x) \mid = \mid V_H(x) \mid \end{align}

In this case, both graph $G$ and graph $H$ have the same number of vertices. It's also good to check to see if the number of edges are the same in both graphs. In this case, both graphs have $7$ edges.

The next step is to look at the degree sequence of both graph $G$ and $H$, as their degree sequences should be the same. The degree sequence of $G$ is $(2, 2, 3, 3, 4)$. The degree sequence of $H$ is $(2, 2, 3, 3, 4)$. Now let's see if there exists a bijection function $f$ such that $f: V(G) \rightarrow V(H)$.

We can first acknowledge that $\deg (a)$ in graph $G$ is $4$, and the $\deg (v)$ in graph $H$ is $4$. Hence $\deg (a) = \deg (v)$, so if a bijection exists, then vertices $a$ and $v$ must correspond to each other. It turns out that this graph is isomorphic when we check all of the edges:

Let's try the following bijection:
$f(a) = v$
$f(b) = x$
$f(c) = w$
$f(d) = y$
$f(e) = z$

Edge in G	Correspondence in H
$\{a, b\} \in E(G)$	$\{f(a), f(b) \} \in E(G)$
$\{a, c\} \in E(G)$	$\{f(a), f(c) \} \in E(G)$
$\{a, d\} \in E(G)$	$\{f(a), f(d) \} \in E(G)$
$\{a, e\} \in E(G)$	$\{f(a), f(e) \} \in E(G)$
$\{b, c\} \in E(G)$	$\{f(b), f(c) \} \in E(G)$
$\{b, d\} \in E(G)$	$\{f(b), f(d) \} \in E(G)$
$\{c, e\} \in E(G)$	$\{f(c), f(e) \} \in E(G)$

Thus since there are $7$ edges in both $G$ and $H$ and there is a bijection $f : V(G) \to V(H)$ then $G \cong H$.