How to Compare Special Graphs
Two graphs can look different because their vertices have different names, even when their adjacency structure is identical. Conversely, graphs can share several numerical properties and still have different structures. A reliable comparison uses two complementary methods: find a bijection that preserves adjacency to prove isomorphism, or find a structural invariant that differs to prove non-isomorphism.
All graphs in this tutorial are finite, simple and undirected. For an edge \(uv\), the vertices \(u\) and \(v\) are its endpoints. A triangle is a cycle of length \(3\), and a cycle of length \(4\) is called a 4-cycle.
The labels themselves have no structural meaning. What matters is whether the bijection preserves which pairs are adjacent. Before trying to construct a bijection, it is often faster to compare basic quantities that every isomorphism must preserve.
Invariants: Quick Tests Before Building a Bijection
Proof. Let \(f:V(G)\to V(H)\) be an isomorphism. Since \(f\) is a bijection, \(|V(G)|=|V(H)|\). The map sending each edge \(uv\in E(G)\) to \(f(u)f(v)\) sends edges to edges. It is one-to-one because \(f\) is one-to-one, and it is onto \(E(H)\) because the “if and only if” condition also preserves edges in the reverse direction. Thus \(|E(G)|=|E(H)|\).
For a vertex \(u\), the neighbors of \(u\) map bijectively to the neighbors of \(f(u)\): adjacency is preserved in both directions. Hence \(\deg_G(u)=\deg_H(f(u))\), so the degree multisets agree. Finally, applying \(f\) to the vertices of any cycle gives a cycle of the same length in \(H\). Applying \(f^{-1}\) reverses this correspondence, so the numbers of cycles of each fixed length agree. \(\square\)
These tests are necessary, not sufficient: matching invariants do not automatically give an isomorphism. A failed test is decisive, however. If the orders, sizes, degree multisets, or cycle counts differ, the graphs cannot be isomorphic.
Worked Example: Complete Versus Star
Let \(G=K_4\), with \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,14,23,24,34\}\). Let \(H=K_{1,3}\), with \(V(H)=\{a,b,c,d\}\) and \(E(H)=\{ab,ac,ad\}\). Decide whether \(G\) and \(H\) are isomorphic.
Both graphs have four vertices. The six listed edges of \(G\) give \(\deg(1)=\deg(2)=\deg(3)=\deg(4)=3\), so its degree multiset is \(\{3,3,3,3\}\). In \(H\), vertex \(a\) is incident with all three edges, while \(b,c,d\) are each incident with one edge. Its degree multiset is \(\{3,1,1,1\}\).
Check: the edge counts are \(6\) for \(G\) and \(3\) for \(H\), computed directly from their edge sets. Both the degree multisets and sizes differ, so no bijection can preserve adjacency. The graphs are not isomorphic.
Proving Isomorphism by Relabelling
To prove that two graphs are isomorphic, give a bijection and check adjacency. One efficient method is to define the second graph’s edges as the images of the first graph’s edges under the proposed bijection. For an explicit case study, the check below lists all corresponding edges, so both the map and its adjacency behavior can be verified directly.
Worked Example: Two Labelings of a Complete Bipartite Graph
Let \(G\) have vertex set \(\{a,b,1,2,3\}\) and edge set \(\{a1,a2,a3,b1,b2,b3\}\). Let \(H\) have vertex set \(\{u,v,x,y,z\}\) and edge set \(\{ux,uy,uz,vx,vy,vz\}\). These are two labelled versions of \(K_{2,3}\).
Define \(f(a)=u\), \(f(b)=v\), \(f(1)=x\), \(f(2)=y\), and \(f(3)=z\). The five images are distinct and exhaust \(V(H)\), so \(f\) is a bijection. The edges of \(G\) map as follows: \(a1\mapsto ux\), \(a2\mapsto uy\), \(a3\mapsto uz\), \(b1\mapsto vx\), \(b2\mapsto vy\), and \(b3\mapsto vz\). These are exactly the six edges of \(H\). Every other pair of distinct vertices in \(G\) has both vertices in \(\{a,b\}\) or both in \(\{1,2,3\}\); its image lies within \(\{u,v\}\) or within \(\{x,y,z\}\), respectively, and is a nonedge in \(H\). Thus nonedges are preserved as well.
Check: both graphs have five vertices and six edges. Each has two vertices of degree \(3\) and three of degree \(2\), as the displayed edge sets show. The explicit bijection proves the stronger claim that the graphs are isomorphic.
Complete graphs are another useful family for comparison. In \(K_n\), every pair of distinct vertices is adjacent, so any bijection between the vertex sets of two complete graphs of the same order is an isomorphism: every pair maps to an edge. If their orders differ, no bijection exists. In particular, the order settles the comparison for complete graphs, while a bijection verifies the equal-order case.
Case Study: The Three-Dimensional Cube
The vertices of the cube graph \(Q_3\) are binary strings of length three, with two strings adjacent when they differ in exactly one position. This definition uses vertex labels that are not letters or numbers in a drawing. A different labeling can still describe the same graph, provided an explicit bijection carries each adjacency across.
Worked Example: Binary Strings and Letter Labels for \(Q_3\)
Let \(G=Q_3\), with \(V(G)=\{000,001,010,011,100,101,110,111\}\). By the one-bit-difference rule, its edge set is \(\{000\text{-}001,000\text{-}010,000\text{-}100,001\text{-}011,001\text{-}101,010\text{-}011,010\text{-}110,011\text{-}111,100\text{-}101,100\text{-}110,101\text{-}111,110\text{-}111\}\). Here a hyphen separates two string labels forming an edge.
Let \(H\) have vertex set \(\{a,b,c,d,e,f,g,h\}\) and edge set \(\{ab,ac,ae,bd,bf,cd,cg,dh,ef,eg,fh,gh\}\). Define \(f\) by \(000\mapsto a\), \(001\mapsto b\), \(010\mapsto c\), \(011\mapsto d\), \(100\mapsto e\), \(101\mapsto f\), \(110\mapsto g\), and \(111\mapsto h\). This is a bijection because each of the eight vertices of \(H\) appears exactly once. In the order listed for \(G\), the twelve edges map to \(ab,ac,ae,bd,bf,cd,cg,dh,ef,eg,fh,gh\), exactly the edge set of \(H\). Each vertex of \(G\) has three neighbors, one for changing each bit, and the listed image edges give each vertex of \(H\) degree \(3\).
Check: the edge list of \(G\) contains \(12\) edges, and the edge list of \(H\) also contains \(12\) edges. The displayed bijection carries the full edge set onto the other, so \(G\) and \(H\) are isomorphic.
Case Study: The Petersen Graph and a Prism
Regularity is a useful first comparison, but it does not identify a graph. A graph is 3-regular if every vertex has degree \(3\). The Petersen graph and the pentagonal prism below are both 3-regular and have the same order and size. A cycle count distinguishes them.
Worked Example: Petersen Graph Versus Pentagonal Prism
Use indices \(0,1,2,3,4\), with subscripts interpreted modulo \(5\). Define the Petersen graph \(P\) by \(V(P)=\{a_0,a_1,a_2,a_3,a_4,b_0,b_1,b_2,b_3,b_4\}\) and \(E(P)=\{a_0a_1,a_1a_2,a_2a_3,a_3a_4,a_4a_0,\ a_0b_0,a_1b_1,a_2b_2,a_3b_3,a_4b_4,\ b_0b_2,b_1b_3,b_2b_4,b_3b_0,b_4b_1\}\). The first five edges form the outer cycle, the next five join corresponding \(a_i,b_i\), and the last five form the inner star.
Define the pentagonal prism \(R\) by \(V(R)=\{a_0,a_1,a_2,a_3,a_4,c_0,c_1,c_2,c_3,c_4\}\) and \(E(R)=\{a_0a_1,a_1a_2,a_2a_3,a_3a_4,a_4a_0,\ c_0c_1,c_1c_2,c_2c_3,c_3c_4,c_4c_0,\ a_0c_0,a_1c_1,a_2c_2,a_3c_3,a_4c_4\}\).
Each graph has \(10\) vertices and \(15\) edges, counted from the lists. In \(P\), each \(a_i\) has two neighbors among the \(a\)-vertices and one neighbor \(b_i\); each \(b_i\) has two neighbors among the \(b\)-vertices and one neighbor \(a_i\). In \(R\), each vertex has two neighbors on its 5-cycle and one corresponding vertex on the other cycle. Thus both graphs have degree multiset \(\{3,3,3,3,3,3,3,3,3,3\}\).
However, \(R\) contains the 4-cycle \(a_0,a_1,c_1,c_0,a_0\), since each consecutive pair is an edge in the displayed edge set. To check that \(P\) has no 4-cycle, distinguish its outer vertices \(a_i\) from its inner vertices \(b_i\). An edge between these two groups is one of the five spokes \(a_ib_i\); all other edges stay within one group. Any cycle must use an even number of spokes, since each spoke changes groups and a cycle returns to its starting group. A 4-cycle with no spokes would have to lie entirely in one group, where the edges form a 5-cycle, so none exists. A 4-cycle with four spokes cannot exist because each spoke is disjoint from every other spoke: after traversing one spoke, there is no spoke incident to its endpoint. If a 4-cycle used exactly two spokes, they would be at distinct indices \(i,j\). Its two other edges would have to be one outer edge \(a_ia_j\) and one inner edge \(b_ib_j\). The outer edge requires \(j=i+1\) or \(i-1\) modulo \(5\); the inner edge requires \(j=i+2\) or \(i-2\) modulo \(5\). These possibilities do not overlap. Therefore \(P\) has no 4-cycle.
Check: a 4-cycle exists in \(R\) and not in \(P\), although their orders, sizes, and degree multisets agree. By the invariant proposition, the graphs are not isomorphic.
A Common Mistake: Equal Degrees Do Not Settle the Question
It is tempting to treat equal degree multisets as a proof of isomorphism. The Petersen/prism comparison already shows why that fails: the degrees agree but the cycle structure does not. Even a small example makes the limitation clear.
Let \(G\) have \(V(G)=\{1,2,3,4,5,6\}\) and \(E(G)=\{12,23,34,45,56,61\}\). Let \(H\) have \(V(H)=\{a,b,c,d,e,f\}\) and \(E(H)=\{ab,bc,ca,de,ef,fd\}\). Each vertex in each graph has degree \(2\), and each edge list has six edges. But \(H\) contains the triangle \(abc\), whereas \(G\) has no triangle: the two neighbors of each vertex in \(G\) are not adjacent to each other. Since isomorphisms preserve triangles, \(G\) and \(H\) are not isomorphic.
The incorrect conclusion would be: “Both graphs have six vertices and every degree is \(2\), so they are isomorphic.” The correction is to use matching invariants only as a screening test. To prove isomorphism, verify a bijection; to disprove it, exhibit an invariant that differs.
A Practical Comparison Checklist
If the vertex counts or edge counts differ, the graphs are not isomorphic.
Check the full degree multiset, not only the maximum or minimum degree.
For these special graphs, useful checks include triangles, 4-cycles, and the sizes of the parts in a stated bipartition.
Write the map on every vertex and check that its edge images are exactly the target edge set.
This order of work avoids two common inefficiencies: attempting to construct a complicated map before noticing a degree mismatch, and mistaking a collection of necessary conditions for a proof. Isomorphism is ultimately a statement about all vertex pairs, so a successful map must preserve both edges and nonedges.
Check Your Understanding
For each comparison, decide what can be concluded and state the decisive check.
- Can \(K_5\) be isomorphic to a graph on five vertices with only eight edges? Explain.
- Give a bijection proving that the graph with vertices \(\{p,q,r\}\) and edges \(\{pq,qr\}\) is isomorphic to the graph with vertices \(\{1,2,3\}\) and edges \(\{12,13\}\).
- Why does equality of degree multisets not prove that two graphs are isomorphic?
- Which invariant distinguishes the Petersen graph from the pentagonal prism in the worked example?
- For a proposed vertex bijection, why should nonedges be checked as well as edges?