Problem: Iso, You So

An important problem in graph theory is graph isomorphism. An isomorphism in mathematics is a structure-preserving invertible mapping between two objects. It describes how one object can be transformed into another and vice versa. Isomorphism corresponds closely (but is not equivalent!) to our traditional notion of equality. Equal objects are identical objects; isomorphic objects are mutually convertible objects.

Consider the formal definition of graph isomorphism:

Because of this additional property, we colloquially call a graph isomorphism an edge-preserving mapping between \(G_1\) and \(G_2\).

1. First, let’s explore this definition. Give a small, artificial example of two graphs and an isomorphism between them.

2. Next, give a real-world example of two graphs and an isomorphism between them. Choose such an example where the notion of isomorphism might be useful to know. In a sentence, justify your choice of example.

3. For the remainder of this problem, you will prove properties of graphs involving isomorphisms. Before doing so, let’s make sure we understand the definition of graph isomorphism from a proof context. Suppose that we have graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\). In a few sentences, answer the following:

   • Suppose we are trying to prove that \(G_1\) and \(G_2\) are isomorphic. What must we construct in order to prove this fact?
   • Suppose we assume that \(G_1\) and \(G_2\) are isomorphic. What do we know exists because of this assumption?

4. First, let’s crystallize the notion of isomorphism as “closely corresponding” to equality. Define the binary relation \(\mathsf{ISO}(G_1, G_2)\) to mean that \(G_1\) and \(G_2\) are isomorphic. Prove the following claim about \(\mathsf{ISO}\):

   Claim: \(\mathsf{ISO}\) is an equivalence relation.

5. Now, let’s talk about finding isomorphisms in a restricted case: trees. Let \(T_1\) and \(T_2\) be trees. Consider the following recursive definition of an algorithm for determining whether \(T_1\) and \(T_2\) are isomorphic:

   • If \(T_1\) and \(T_2\) are both empty, then they are (trivially) isomorphic.

   • If \(T_1\) and \(T_2\) are both non-empty, then they are isomorphic if either:

     • Their left children are recursively isomorphic and their right children are recursively isomorphic, or
     • The left child of \(T_1\) is isomorphic with the right child of \(T_2\) and the right child of \(T_1\) is isomorphic with the left child of \(T_2\).

   • If one of \(T_1\) and \(T_2\) is empty and the other is non-empty, then they are not isomorphic.

   Call this recursive algorithm \(\mathsf{isIso}\).

6. Give a small artificial examples of a tree where \(\mathsf{isIso}\) reports that the tree is isomorphic as well as a small, artificial example of a tree where \(\mathsf{isIso}\) reports that the tree is not isomorphic. (Hint: try to pick examples that will test your knowledge of how the algorithm works. This mini-exercise is to prepare you for the next proof!)

7. Prove the following fact about \(\mathsf{isIso}\):

   Claim (\(\mathsf{isIso}\) Soundness): For any trees \(T_1\) and \(T_2\), if \(\mathsf{isIso}(T_1, T_2)\) reports true, then \(T_1\) and \(T_2\) are isomorphic.

   To prove this claim, use mutual induction on the structure of \(T_1\) and \(T_2\). In mutual induction, we construct both trees simultaneously. Consequently, our induction hypothesis applies whenever we are considering any of the children of both input trees.

   (N.B., we leave as an exercise to the reader the related proof of completeness of the algorithm, i.e., if the trees are isomorphic, then the algorithm reports true.)

8. Finally, let’s consider finding isomorphisms over general graphs, not just trees. In a few sentences, explain why we cannot simply apply this tree isomorphism algorithm to a general graph?

   (Hint: play with example graphs of a variety of shapes and size and observe where the tree isomorphic algorithm breaks down in the general case.)