Graph isomorphism

In the field of graph theory, mathematicians study the structure of networks. A graph consists of vertices, which are points, and edges, which are the lines connecting them. Sometimes, two graphs look completely different when drawn on a page.

One might look like a simple circle, while the other looks like a tangled web.

However, they might actually share the exact same structural pattern. This concept is known as graph isomorphism. Two graphs are isomorphic if they are structurally identical, even if their visual representations differ.

To prove two graphs are isomorphic, we must find a specific type of mapping called a bijection. A bijection is a rule that pairs every vertex in the first graph with exactly one unique vertex in the second graph. This mapping must be an edge-preserving bijection. This means that if any two vertices are connected by an edge in the first graph, their corresponding partners must also be connected in the second graph. If such a mapping exists, the graphs belong to the same isomorphism class. This relationship is an equivalence relation, which allows mathematicians to group all possible graphs into these distinct classes.

There are different ways to define isomorphism depending on the type of graph being studied. The basic definition applies to undirected, non-labeled, and non-weighted graphs. However, we can add more rules for other structures. For example, in directed graphs, the mapping must preserve the direction of the arcs. In weighted graphs, the mapping must preserve the weights assigned to the edges. Labeled graphs are more complex and have two different definitions in use. One definition requires the mapping to preserve both the edges and the specific labels. Another definition only requires preserving the equivalence classes of labels, meaning vertices with equivalent labels must map to each other.

An interesting special case occurs when a graph is mapped onto itself. This type of isomorphism is called an automorphism. When we study the history of these ideas, we find important theorems like the Whitney graph isomorphism theorem. Hassler Whitney showed that two connected graphs are isomorphic if and only if their line graphs are isomorphic. A line graph is a different way of representing the connections between edges. There is one famous exception to this rule. The complete graph on three vertices, known as K3, and the complete bipartite graph K1,3, are not isomorphic.

Despite this, they both share K3 as their line graph.

In computer science, determining if two graphs are isomorphic is a major challenge. This is known as the graph isomorphism problem. It is a significant puzzle because of its place in computational complexity theory. The problem belongs to a class called NP, but it is not known to be in P or to be NP-complete. It is one of only two problems among twelve standard problems where the complexity remains unresolved. The other mystery problem is integer factorization. In November 2015, László Babai from the University of Chicago claimed a breakthrough. He suggested the problem could be solved in quasi-polynomial time. Although he briefly retracted the claim in 2017, he later restored the original result.

This mathematical concept has many practical uses in modern technology. In the field of cheminformatics, scientists use it for the identification of chemical compounds. Electronic design automation also relies on it to verify that different representations of a circuit design are equivalent. Computer scientists use various algorithms to solve these problems. The Weisfeiler-Leman test is a heuristic method used to check for isomorphism. While it can prove two graphs are different, it cannot always prove they are the same. Another tool is the vf2 algorithm, developed by Cordella and others in 2001. This is a depth-first search algorithm that builds an isomorphism incrementally.

Even though the vf2 algorithm has a worst-case exponential time complexity, it works very well in practice. It can efficiently handle graphs containing thousands of nodes. This makes it useful for pattern recognition, computer vision, and bioinformatics. Understanding isomorphism helps us separate the true properties of a structure from how it is drawn. For instance, if a graph has exactly one cycle, every graph in its isomorphism class will also have exactly one cycle. By focusing on these underlying connections, we can understand the fundamental nature of complex networks.