Non-Isomorphic Graphs

In the study of networks, a fundamental question arises: when are two networks, or graphs, structurally the same, just drawn differently? This is the essence of the graph isomorphism problem. While proving two graphs are identical involves finding a direct mapping, proving they are different presents a unique and fascinating challenge. Given that brute-force comparison is computationally impossible for all but the smallest graphs, we must rely on cleverer, more elegant methods to establish structural distinction. This article delves into the strategies for proving non-isomorphism, providing a toolkit for identifying fundamental differences in graph structures.

The following chapters will guide you through this intriguing area of graph theory. In "Principles and Mechanisms," we will explore the core concept of graph invariants—from simple properties like vertex and edge counts to more sophisticated fingerprints like graph spectra and polynomials—and see how their failures reveal the problem's subtlety. Subsequently, in "Applications and Interdisciplinary Connections," we will uncover the profound impact of non-isomorphism, showing how this theoretical concept provides practical solutions in fields like chemistry and drives deep questions in theoretical computer science.

Imagine you are given two tangled knots of string. Are they the same knot, just twisted differently, or are they fundamentally distinct? This is the spirit of the graph isomorphism problem. We want to know if two graphs—two networks of dots and lines—are structurally identical, regardless of how they are drawn or how their vertices are labeled. Proving they are the same requires finding a perfect one-to-one mapping, a structural dictionary that translates one graph into the other. But how do we prove they are not the same?

We can't just try every possible mapping. For a graph with a modest 60 vertices, the number of potential mappings is $60!$, a number far larger than the estimated number of atoms in the universe. A brute-force check is out of the question. Instead, we must think like a detective. We must look for a ​​graph invariant​​—a quantifiable property of the graph's structure that remains unchanged no matter how you draw or relabel it. If we can find just one such invariant that differs between two graphs, we have our proof. They are ​​non-isomorphic​​. This strategy of finding a distinguishing, easy-to-check property is the heart of proving non-isomorphism in a verifiable way.

The most basic invariants are the ones you'd check first. How many vertices are there? How many edges? If these numbers don't match, the case is closed. But what if they do?

Consider graphs with 5 vertices and 4 edges. We could have a simple path, like five towns in a row connected by a single road ($P_5$). Or we could have a central town connected to four other towns, like a star ($K_{1,4}$). Both have 5 vertices and 4 edges, but their structures feel different. One simple invariant that captures this is ​​connectivity​​. The path and the star are both connected—you can get from any vertex to any other. But what if we had a graph made of a triangle ($C_3$) and a separate pair of connected vertices ($P_2$)? This also has 5 vertices and 4 edges, but it's in two separate pieces. It is disconnected. Since connectivity is an invariant, a connected graph can never be isomorphic to a disconnected one. This gives us a simple, powerful tool to distinguish graphs that might otherwise look similar in their basic counts.

A more refined invariant is the ​​degree sequence​​, which is simply a list of the number of connections for each vertex, sorted in descending order. For instance, the path graph on five vertices ($P_5$) has two endpoints with one connection each and three internal vertices with two connections each, giving it a degree sequence of $(2, 2, 2, 1, 1)$. The star graph ($K_{1,4}$) has one central vertex with four connections and four outer vertices with one connection each, giving a degree sequence of $(4, 1, 1, 1, 1)$. Since their degree sequences are different, they cannot be isomorphic.

For a while, one might wonder if the degree sequence is the ultimate fingerprint. If two graphs have the same number of vertices, edges, and the exact same degree sequence, aren't they bound to be the same? The answer, perhaps surprisingly, is a resounding no.

Let's look at one of the most famous counterexamples in introductory graph theory. Consider a single, large loop of six vertices—a hexagon, or $C_6$. Now, imagine a different graph made of two separate, disjoint triangles ($2K_3$). Let's check their invariants.

• Both graphs have 6 vertices.
• Both graphs have 6 edges (the hexagon has 6, and two triangles have $3+3=6$).
• In the hexagon, every vertex is connected to exactly two neighbors. The degree sequence is $(2, 2, 2, 2, 2, 2)$.
• In the pair of triangles, every vertex is also connected to exactly two others within its own triangle. The degree sequence is also $(2, 2, 2, 2, 2, 2)$.

Their most obvious fingerprints match perfectly. Yet, they are fundamentally different. The hexagon is connected, while the two triangles are not. This demonstrates dramatically that the degree sequence is not a complete invariant. It can't distinguish between all non-isomorphic graphs.

This isn't just about connectivity. Even among connected graphs, the degree sequence can deceive us. Another structural property we can look at is a graph's ​​girth​​, defined as the length of its shortest cycle. For our hexagon ($C_6$), the shortest (and only) cycle has length 6. For the pair of triangles ($2K_3$), the shortest cycle has length 3. This difference in girth is another proof of their non-isomorphism, and it highlights that the degree sequence does not determine properties like girth. The existence of such pairs means that simply counting connections isn't enough; the pattern of those connections is what truly matters.

The failure of simple invariants led mathematicians to seek more powerful, sophisticated tools—invariants that capture the deeper structure of a graph. These are the equivalent of forensic DNA analysis.

One such tool is the ​​spectrum​​ of a graph. By representing a graph as a matrix (its adjacency matrix) and calculating the eigenvalues of that matrix, we get a set of numbers that is a powerful graph invariant. It's a fundamental theorem that isomorphic graphs must have the same spectrum—they must be ​​cospectral​​. So, if you compute the spectra of two graphs and they differ, you have a definitive proof of non-isomorphism.

For a long time, it was hoped that the spectrum might be the "magic" fingerprint, a complete invariant. But in 1957, a pair of non-isomorphic, cospectral graphs was discovered. This means two structurally different graphs can produce the exact same set of eigenvalues. Therefore, using the spectrum as a test for isomorphism is a one-way street: a different spectrum proves non-isomorphism, but the same spectrum proves nothing.

An even more powerful tool is the ​​Tutte polynomial​​, an incredible two-variable polynomial that encodes a vast amount of combinatorial information about a graph, such as the number of spanning trees and how to color the graph. It is an extremely strong invariant. If two graphs have different Tutte polynomials, they are certainly not isomorphic. Could this be the final answer? Alas, no. Just as with spectra, mathematicians have found clever examples of non-isomorphic graphs that share the exact same Tutte polynomial. The hunt for a single, easily-computed, complete invariant continues, and its difficulty is a testament to the profound complexity hidden in simple networks.

The difficulty in finding such a perfect fingerprint is also reflected in computational approaches. The ​​Weisfeiler-Lehman (WL) test​​ is an algorithm that tries to distinguish graphs by iteratively refining a "coloring" of their vertices. It starts by assigning each vertex a color based on its degree. Then, in each step, it gives a vertex a new color based on its own color and the collection of its neighbors' colors. If at any point the palette of colors differs between two graphs, they are non-isomorphic. However, for some highly symmetric graphs, like two different "regular" graphs where all vertices have the same degree, this test can run forever without ever finding a difference, even if the graphs are non-isomorphic. This reveals the subtle nature of the problem, which sits in a fascinating gray area of computational complexity—not known to be easy, but not proven to be among the hardest problems either.

After this journey through failed attempts and subtle difficulties, it might seem that finding a perfect structural fingerprint is a hopeless task. But in some areas of graph theory, there are surprising and beautiful successes. One such success involves ​​line graphs​​.

The line graph $L(G)$ of a graph $G$ is a new graph you build by turning the edges of $G$ into the vertices of $L(G)$. Two vertices in the new line graph are connected if their corresponding edges in the original graph shared a vertex. This transformation is itself a kind of invariant. The question is, is it a complete one?

The ​​Whitney Isomorphism Theorem​​ provides an astonishingly clean answer. It states that for any two connected graphs $G_1$ and $G_2$ with more than 4 vertices, if their line graphs are isomorphic ($L(G_1) \cong L(G_2)$), then the original graphs must have been isomorphic too ($G_1 \cong G_2$). Outside of very small graphs, the line graph acts as a near-perfect fingerprint!

But why the caveat about "more than 4 vertices"? Nature loves to play with exceptions, and this theorem has one of the most elegant in all of mathematics. Consider the triangle ($K_3$) and the "claw" graph ($K_{1,3}$), which is a central vertex connected to three others. The triangle has 3 vertices and is full of cycles. The claw has 4 vertices and is a tree (no cycles). They are clearly non-isomorphic. But let's look at their line graphs:

• In $K_3$, there are three edges, and every edge shares a vertex with the other two. So, its line graph is a triangle of three vertices, i.e., $L(K_3) \cong K_3$.
• In $K_{1,3}$, there are also three edges, and all three meet at the central vertex. This means their corresponding vertices in the line graph are all mutually connected. The result is also a triangle, $L(K_{1,3}) \cong K_3$.

Here we have it: a single, exceptional pair of non-isomorphic graphs—$\{K_3, K_{1,3}\}$—that produce the same line graph. This beautiful anomaly is precisely why the theorem needs its condition on the number of vertices. It's a perfect illustration of how in mathematics, even the exceptions to the rules are themselves governed by a deep and elegant logic. The quest to understand when two structures are the same or different is a journey from simple observations to deep complexities, punctuated by moments of surprising clarity.

We have spent some time understanding the machinery of graph theory, learning to see when two intricate webs of connections are, in essence, the same picture drawn differently. This is the idea of isomorphism. But as is often the case in science, the real fun begins when things are different. The concept of non-isomorphism—of fundamental, undeniable difference in structure—is not merely a statement of what isn't, but a gateway to a world of profound applications and deep intellectual puzzles. It touches everything from the molecules in our bodies to the very limits of computation and the nature of proof itself.

Let us begin with something tangible: a molecule. In medicinal chemistry, scientists hunt through vast digital libraries containing millions of molecular structures, searching for a candidate that could become a life-saving drug. An acyclic molecule, with its atoms and bonds, can be thought of as a tree graph. Different molecules with the same chemical formula—for instance, two variants of pentane, $\text{C}_5\text{H}_{12}$—are what chemists call structural isomers. In our language, they are simply non-isomorphic graphs.

Now, imagine you have a target molecule and a database of ten million candidates. How do you find which ones are structurally identical to your target? You could try to find a mapping, an isomorphism, for each one. But this is computationally very slow, like trying to match a master key to ten million different, complex locks. Here, the power of non-isomorphism comes to our rescue in a practical way. Instead of trying to prove two graphs are the same, we can often prove they are not with a simple, quick test.

We can compute a "fingerprint" of a graph, a property that must be the same for any two isomorphic graphs. Such a property is called a ​​graph invariant​​. The simplest invariants are the number of vertices (atoms) and edges (bonds). But a much more powerful and still rapidly computable invariant is the ​​degree sequence​​: a sorted list of the number of connections for each atom. If two molecular graphs have different degree sequences, they cannot possibly be isomorphic. There is no need for the laborious process of checking all possible mappings; we can discard the candidate immediately. This simple "pre-screening" check, which works by proving non-isomorphism, is a cornerstone of computational chemistry and network science, allowing us to sift through immense haystacks of data to find the few needles that matter.

This challenge of telling structures apart is not just a practical hurdle; it is a window into one of the most celebrated problems in theoretical computer science. The decision problem "Are these two graphs isomorphic?" is known as Graph Isomorphism, or GI. It sits in a strange place in the landscape of computational complexity. We know that if the answer is "yes," there is a simple proof: the isomorphism mapping itself. A computer can quickly check if a given mapping works. This places GI in the complexity class NP.

But what about the complementary problem, Graph Non-Isomorphism (GNI): "Are these two graphs not isomorphic?". If the answer is "yes," what is the proof? You can't just show one failed mapping; you must somehow demonstrate that no possible mapping can exist. This seems much harder! And yet, GNI has a beautiful and surprising property: it belongs to a class called co-NP, which means a "yes" answer to non-isomorphism also has a short, verifiable proof.

What could such a proof possibly look like? The answer came from a wonderful new way of thinking about computation: ​​interactive proofs​​. Imagine a game between an all-powerful but potentially untrustworthy Prover (let's call him Merlin) and a skeptical, computationally limited Verifier (Arthur).

Let's frame this with a puzzle. Suppose you have two 9x9 Sudoku puzzles, and you claim they are fundamentally different—not just in the given numbers, but in their underlying structure of constraints. You want to prove this to a friend without giving any clues about how to solve either one. You could use the following game: Your friend secretly picks one of the two puzzles, randomly shuffles the numbers (e.g., all 2s become 5s, all 3s become 7s, etc.), and shows you the result. Your task is simply to say which puzzle they started with.

If the two Sudoku puzzles were structurally identical (isomorphic), then any shuffled version of one would be indistinguishable from a shuffled version of the other. You would have no information and could only guess, getting it right about half the time. But if they are truly, structurally non-isomorphic, then their "families" of shuffled versions are completely separate. With your superior insight (or, for Merlin, unlimited computational power), you can analyze the structure of the shuffled puzzle and always determine its origin. By repeating this game, you can convince your friend, with near-perfect certainty, that the original puzzles must have been different.

This is the essence of the "Arthur-Merlin" protocol for Graph Non-Isomorphism. Arthur, the verifier, secretly picks one of two graphs, $G_1$ or $G_2$, randomly permutes its vertex labels to create a new graph $H$, and shows $H$ to Merlin. If $G_1$ and $G_2$ are non-isomorphic, their isomorphism classes—the sets of all graphs that look like them—are disjoint. Merlin, with his infinite power, can see which class $H$ belongs to and correctly report the original graph. If $G_1$ and $G_2$ are isomorphic, the two classes are identical, and $H$ gives no information about Arthur's choice. Merlin is forced to guess.

The magic here is twofold. First, it relies on randomness as a computational tool. Second, it hinges on Arthur's choice being a secret. If Arthur were to announce which graph he chose before Merlin answered, the game would be trivial; Merlin could just repeat the choice back, proving nothing.

This leads to a final, subtle twist. Could Merlin use the same game to prove two graphs are isomorphic? Suppose he knows the isomorphism. He could always answer Arthur's challenge, even if Arthur asks him to map between the two different original graphs. The protocol would appear to work. But it would fail a crucial test: the ​​zero-knowledge​​ property. In the non-isomorphism game, Arthur learns nothing he couldn't have figured out himself. But in the isomorphism game, Merlin might have to reveal a permutation that connects the two graphs—a piece of knowledge, a solution to the isomorphism problem, that Arthur could not have computed. This violates the rule of revealing nothing but the truth of the statement, a failure that highlights the deep and beautiful asymmetry between proving a positive and proving a negative.

Let us now step back and ask a grander question. We know what it means for graphs to be different, but just how many different graphs are there? If we have, say, 5 vertices, we can draw an edge or not between any pair. There are $\binom{5}{2}=10$ possible pairs, so there are $2^{10} = 1024$ ways to draw a graph if we consider the vertices to be labeled. But most of these are just disguised versions of each other. How many truly distinct, non-isomorphic graphs on 5 vertices exist?

The answer, it turns out, is 34. This number is not arrived at by drawing them all out—a task that quickly becomes impossible as the number of vertices grows. Instead, it is found using one of the crown jewels of mathematics: the application of group theory to combinatorics. The problem of counting non-isomorphic structures is equivalent to counting the orbits of a set under a group action. Here, the set is all 1024 labeled graphs, and the group is the symmetric group $S_5$ acting by permuting the vertices. Using a powerful result known as Burnside's Lemma, mathematicians can perform this "impossible" count with an elegant calculation. This reveals a stunning unity between the study of symmetry (group theory) and the study of discrete structures (graph theory).

Finally, to appreciate the delightful weirdness of non-isomorphism, let us look at a few curiosities that challenge our intuition. We might think of two non-isomorphic graphs as fundamentally and permanently different. But consider two distinct tree structures. It is possible to choose one edge in each, perform a simple "subdivision" operation (turning an edge into a path of length two), and have the two resulting, larger trees become perfectly isomorphic!. This is like two different people taking one small, different step and ending up in the exact same place. Difference, it seems, can be a fragile thing.

Or consider graphs drawn on a plane. For any such graph, we can construct its "dual," where faces become vertices and shared edges become connections between them. One might assume that if two planar graphs are non-isomorphic, their duals must be too. But this is not so! There exist pairs of non-isomorphic planar graphs whose duals are perfectly isomorphic. "Sameness" depends entirely on the lens through which you are looking.

Even when two non-isomorphic graphs share many properties—the same number of vertices, the same number of edges, every vertex having exactly three neighbors—their inner structure can be worlds apart. The prism graph (two triangles connected by a matching) and the complete bipartite graph $K_{3,3}$ are both 3-regular on 6 vertices. One contains triangles; the other, being bipartite, contains no odd cycles at all. They are fundamentally different, as shown by their non-isomorphic complements: the complement of the prism graph is a 6-cycle ($C_6$), while the complement of $K_{3,3}$ is two disjoint triangles ($2K_3$).

From the practicalities of drug design to the philosophical depths of computational proof, the simple question of whether two things are the same or different opens up entire worlds. By studying what it means for graphs to be non-isomorphic, we do not simply create a catalogue of differences. We gain a deeper appreciation for the rich and varied tapestry of structure itself, and for the elegant and often surprising ways in which these structures populate our mathematical universe.