Combinatorics

Section 11.4 Isomorphism of graphs

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

Which of these graphs is \(K_2\text{?}\) 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.

So a graph isomorphism is a bijection between the vertex sets 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 the key defining relation or relations of the structures they were mapping. For graphs, the key relation is which vertices are adjacent to each other. If that is preserved, then the networks being represented are for all intents and purposes, the same.

You may have seen previously that 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\text{,}\) 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\text{,}\) 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\text{,}\) we have \(G \cong G\) by the identity map on the vertices;

• for any graphs \(G_1\) and \(G_2\text{,}\) we have

  \begin{equation*} G_1 \cong G_2 \Leftrightarrow G_2 \cong G_1\text{,} \end{equation*}

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

  \begin{equation*} \{v,w\} \in E_1 \Leftrightarrow \{\varphi(v),\varphi(w)\} \in E_2 \end{equation*}

  is equivalent to

  \begin{equation*} \{\varphi^{-1}(v),\varphi^{-1}(w)\} \in E_1 \Leftrightarrow \{v,w\} \in E_2; \end{equation*}

• for any graphs \(G_1\text{,}\) \(G_2\text{,}\) and \(G_3\) with \(\varphi_1\colon G_1\to G_2\) and \(\varphi_2\colon G_2\to G_3\) being isomorphisms, the composition \(\varphi_2\circ \varphi_1\colon G_1 \to G_3\) is a bijection, and

  \begin{equation*} \{v,w\} \in E_1 \Leftrightarrow \{\varphi_1(v),\varphi_1(w)\} \in E_2 \Leftrightarrow \{\varphi_2(\varphi_1(v)),\varphi_2(\varphi_1(w))\} \in E_3\text{,} \end{equation*}

  so \(G_1 \cong G_3\text{.}\)

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.

The graphs \(G\) and \(H\text{:}\)

are isomorphic. The map \(\varphi\) defined by

• \(\varphi(a)=v\text{;}\)

• \(\varphi(b)=z\text{;}\)

• \(\varphi(c)=y\text{;}\)

• \(\varphi(d)=x\text{;}\)

• \(\displaystyle \varphi(e)=w\)

is an isomorphism. It is straightforward (though perhaps tedious) to check that each of the \(5\) edges of \(G\) maps to one of the five edges of \(H\) under \(\varphi\text{.}\)

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 any function that can be defined on graphs, that must produce the same output 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 efficiently-computable 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 efficiently-computable invariant distinguishes between every pair of non-isomorphic graphs. (We are glossing over some details here. What we have said is true if we mean “computable in polynomial time” when we say “efficiently-computable”. In \(2019\text{,}\) László Babai published an upgrade to the isomorphism test we discuss in the next paragraph, enabling his algorithm to produce an invariant that distinguishes between any pair of nonisomorphic graphs and is computable in quasipolynomial time.)

In case you know what this means (perhaps if you are studying computer science), the graph isomorphism problem is particularly interesting because it is one of a very few natural problems that are known to be in NP but that are not known to be either in P, or to be NP-complete. (Other classical examples are the discrete logarithm and integer factorisation problems.) Although no polynomial time algorithm for solving this problem is known, in \(2015\) (with a minor patch added in \(2017\)) László Babai (1950—) at the University of Chicago found a quasipolynomial time algorithm for solving the graph isomorphism problem. This was a major development in our understanding of algorithmic complexity.

To give a bit more context for the importance of Babai's result without going into detail, we provide short definitions of various possible algorithmic complexities (running times). An algorithm runs in polynomial time if the number of operations it takes is at most \(n^c\) for some constant \(c\text{,}\) where \(n\) is a parameter describing the size of the input. An algorithm requires exponential time if the number of operations it takes is at least \(2^{cn}\) for some positive constant \(c\text{,}\) for all sufficiently large \(n\text{.}\) The best known graph isomorphism test prior to Babai's algorithm required time exponential in \(\sqrt{n}\) (this is better than being exponential in \(n\)). An algorithm is quasipolynomial if the number of operations it takes is at most \(2^{c_1(\log(n))^{c_2}}\) for some positive constants \(c_1\) and \(c_2\text{.}\) Note that if we can find a quasipolynomial algorithm with \(c_2=1\text{,}\) then this would actually run in polynomial time.

We give a few graph invariants in the following proposition.

The graph \(G\) of Example 11.4.3 is not isomorphic to \(K_5\text{,}\) because \(K_5\) has \(\binom{5}{2}=10\) edges by Proposition 11.3.9, 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\text{:}\)

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\text{,}\) \(x\text{,}\) \(y\text{,}\) 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\text{,}\) 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\text{.}\) Therefore, an isomorphism between these graphs is not possible.

Observe that the two graphs

both have \(6\) vertices and \(7\) edges, and each has four vertices of valency \(2\) and two vertices of valency \(3\text{.}\) 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\text{,}\) any isomorphism would have to map \(\{c,f\}\) to \(\{v,z\}\text{.}\) 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\text{.}\) But \(c\) and \(f\) 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, \ldots, n\}\text{.}\) 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, \ldots , n\}\text{.}\) There are \(\binom{n}{2}\) possible edges in total. Any graph is formed by taking a subset of the \(n(n-1)/2\) possible edges. In Example 4.1.1, we learned how to count these: there are \(2^{n(n-1)/2}\) subsets.

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

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

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

When \(n=4\text{,}\) we have \(\binom{4}{2}=6\text{,}\) and \(2^6=64\text{,}\) 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 adjacent 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\text{.}\) From the labeled graphs on \(3\) vertices, you can see that there are four unlabeled graphs on \(3\) vertices. These are:

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. (All of these things could still be hard even if a polynomial time algorithm were found, but without such an algorithm these other questions seem completely out of reach.)