Graph Isomorphisms

Section 4.4 Graph Isomorphisms

Investigate! 4.4.1

Which (if any) of the graphs below are the same?

The graphs above are unlabeled. Usually we think of a graph as having a specific set of vertices. Which (if any) of the graphs below are the same?

How about the graphs described below?

Graph 1:

\(V = \{a, b, c, d, e\}\text{,}\)

\(E = \{\{a,b\}, \{a, c\}, \{a,d\}, \{a,e\}, \{b,c\}, \{d,e\}\}\text{.}\)

Graph 2:

\(V = \{v_1, v_2, v_3, v_4, v_5\}\text{,}\)

\(E = \{\{v_1, v_3\}, \{v_1, v_5\}, \{v_2, v_4\}, \{v_2, v_5\}, \{v_3, v_5\}, \{v_4, v_5\}\}\text{.}\)

A graph can be represented by a picture in many ways. For example both of these pictures represent the same graph. They describe the same pattern of connections.

Even if two graphs are not drawn and labelled exactly the same, they might be basically the same. The graphs below describe the same relationships between vertices, even if they are labelled differently.

We call graphs such as these isomorphic . Intuitively, graphs are isomorphic if they describe the same relationships, or better yet, if they are the same except for the names of the vertices. To make the concept of renaming vertices precise, we give the following definitions:

Definition 4.4.1 Isomorphic Graphs

An isomorphism between two graphs \(G_1\) and \(G_2\) is a \(f:V_1 \to V_2\) that creates a one-to-one matching between the vertices of the graphs such that if \(\{a,b\}\) is an edge in \(G_1\) then \(\{f(a), f(b)\}\) is an edge in \(G_2\text{.}\)

Two graphs are isomorphic if there is an isomorphism between them. In this case we write \(G_1 \isom G_2\text{.}\)

An isomorphism is simply a function which renames the vertices. It must be a one-to-one matching so every vertex gets a new name. These newly named vertices must be connected by edges precisely if they were connected by edges with their old names.

Example 4.4.2

Decide whether the graphs below are isomorphic.

Solution

Notice that in \(G_1\text{,}\) the vertex \(a\) is adjacent to every other vertex. In \(G_2\text{,}\) there is also a vertex with this property: \(c\text{.}\) So build the pairing \(g\) by defining \(g(a) = c\) to start with. Next, where should we send \(b\text{?}\) In \(G_1\text{,}\) the vertex \(b\) is only adjacent to vertex \(a\text{.}\) There is exactly one vertex like this in \(G_2\text{,}\) namely \(d\text{.}\) So let \(g(b) = d\text{.}\) As for the last two, in this example, we have a free choice: let \(g(c) = b\) and \(g(d) = a\) (switching these would be fine as well).

Subsection Exercises

1

Is it possible for two different (non-isomorphic) graphs to have the same number of vertices and the same number of edges? What if the degrees of the vertices in the two graphs are the same (so both graphs have vertices with degrees 1, 2, 2, 3, and 4, for example)? Draw two such graphs or explain why not.