Invariants as Isomorphism Tests
When two graphs are presented with different vertex labels, their edge lists may look quite different even if the graphs have the same structure. Isomorphism invariants provide a first way to compare them without guessing how labels correspond. A mismatch in a suitable invariant rules out isomorphism immediately. Agreement is useful for narrowing the possibilities, but it is not, in general, enough to establish isomorphism.
Throughout, graphs are finite and simple. An isomorphism from \(G=(V(G),E(G))\) to \(H=(V(H),E(H))\) is a bijection \(f:V(G)\to V(H)\) such that \(uv\in E(G)\) if and only if \(f(u)f(v)\in E(H)\). A graph property is an isomorphism invariant if isomorphic graphs always have the same value of that property.
Thus, for example, two vertices of degree \(2\) contribute two copies of \(2\) to the degree multiset. Cycle counts can be recorded as \(c_3,c_4,\ldots,c_n\), where \(n=|V(G)|\); a simple graph on \(n\) vertices cannot contain a cycle longer than \(n\).
Which Quantities Must Agree?
Proof. Let \(f:V(G)\to V(H)\) be an isomorphism. Since \(f\) is a bijection, \(|V(G)|=|V(H)|\). Each edge \(uv\) of \(G\) maps to the edge \(f(u)f(v)\) of \(H\). The isomorphism condition also says that every edge of \(H\) arises this way, and distinct edges of \(G\) map to distinct edges of \(H\), since \(f\) is one-to-one. Hence \(|E(G)|=|E(H)|\).
For any vertex \(v\in V(G)\), the map \(f\) sends the neighbors of \(v\) bijectively to the neighbors of \(f(v)\): adjacency is preserved in both directions. Therefore \(\deg_G(v)=\deg_H(f(v))\). As \(f\) pairs every vertex of \(G\) with exactly one vertex of \(H\), the degree multisets agree.
Finally, applying \(f\) to the vertices of a cycle of length \(k\) produces a cycle of length \(k\) in \(H\): consecutive vertices remain adjacent, and distinct vertices remain distinct because \(f\) is one-to-one. Applying \(f^{-1}\) gives the reverse correspondence from cycles of \(H\) to cycles of \(G\). These correspondences are inverse to each other, so the numbers of \(k\)-cycles agree. This holds for every \(k\ge3\). \(\square\)
The theorem gives necessary tests: if even one of the listed quantities differs, the graphs are not isomorphic. It does not say that the quantities determine a graph. A useful comparison begins with the cheapest tests—order and size—and then checks degrees and cycles when needed.
Worked Comparisons
Worked Example: Rejecting Candidates by Order and Size
Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,34\}\). Let \(H\) have \(V(H)=\{a,b,c,d\}\) and \(E(H)=\{ab,bc,cd,da,ac\}\). Could \(G\) and \(H\) be isomorphic?
Both graphs have four vertices, so \(|V(G)|=4=|V(H)|\). The edge counts are \(|E(G)|=3\) and \(|E(H)|=5\). Since an isomorphism would give a bijection between their edge sets, these counts would have to agree. They do not, so \(G\) and \(H\) are not isomorphic.
Check: The degree multiset of \(G\) is \(\{2,2,1,1\}\), obtained from degrees \(1,2,2,1\). For \(H\), the degrees of \(a,b,c,d\) are \(3,2,3,2\), so its degree multiset is \(\{3,3,2,2\}\). This is a second mismatch, consistent with the conclusion.
Worked Example: Rejecting Candidates by Degree Multiset
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,34,45\}\). Let \(H\) have \(V(H)=\{a,b,c,d,e\}\) and \(E(H)=\{ab,ac,ad,be\}\). Compare their invariants.
Each graph has five vertices and four edges. In \(G\), the degrees of vertices \(1,2,3,4,5\), in that order, are \(1,2,2,2,1\): vertices \(1\) and \(5\) each meet one edge, and vertices \(2,3,4\) each meet two. Thus the degree multiset is \(\{2,2,2,1,1\}\).
In \(H\), \(a\) is incident with \(ab,ac,ad\), so \(\deg(a)=3\). Vertex \(b\) is incident with \(ab,be\), so \(\deg(b)=2\). Vertices \(c,d,e\) are each incident with one edge, so their degrees are \(1,1,1\). The degree multiset is therefore \(\{3,2,1,1,1\}\). The multisets differ, so the graphs are not isomorphic despite having the same order and size.
Check: The degree sums are \(2+2+2+1+1=8=2\cdot4\) for \(G\), and \(3+2+1+1+1=8=2\cdot4\) for \(H\). Each sum agrees with twice the edge count, as required by the handshake lemma.
Worked Example: Cycle Counts Separate Graphs with the Same Degrees
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\}\). First compare order, size and degrees, then compare cycle counts.
Both graphs have six vertices and six edges. Every vertex of \(G\) has degree \(2\), since each vertex is incident with its two neighboring edges in the displayed edge set. Every vertex of \(H\) also has degree \(2\): each of \(a,b,c\) is incident with two edges among \(ab,bc,ca\), and each of \(d,e,f\) with two among \(de,ef,fd\). Thus both degree multisets consist of six copies of \(2\).
In \(G\), following the edges gives the cycle \(1,2,3,4,5,6,1\), so \(c_6(G)=1\). There are no shorter cycles: at each vertex, the only two incident edges are already part of this cycle. In \(H\), the edges on \(\{a,b,c\}\) give one triangle and the edges on \(\{d,e,f\}\) give another. No edge joins these two sets, so \(c_3(H)=2\), and \(c_6(H)=0\). The graphs are not isomorphic because their cycle counts differ.
Check: The two listed triangles account for all six edges of \(H\), and each vertex has degree \(2\), giving degree sum \(6\cdot2=12=2\cdot6\). For \(G\), the six edges of the displayed cycle likewise give degree sum \(6\cdot2=12=2\cdot6\). Both computations confirm the stated edge and degree counts.
Matching Tests Do Not Prove Isomorphism
The preceding tests can eliminate candidates, but even agreement on all of them need not settle the question. The next pair has the same order, size, degree multiset and cycle counts, yet the graphs are not isomorphic.
Worked Example: All Listed Counts Agree, but the Graphs Differ
Let \(G\) have \(V(G)=\{a,b,c,d,e,f,g\}\) and \(E(G)=\{ab,ac,ad,be,bf,fg\}\). Let \(H\) have \(V(H)=\{p,q,r,s,t,u,v\}\) and \(E(H)=\{pr,rq,ps,pt,qu,qv\}\).
Each has seven vertices and six edges. In \(G\), the degrees are \(\deg(a)=3\), \(\deg(b)=3\), \(\deg(f)=2\), and \(\deg(c)=\deg(d)=\deg(e)=\deg(g)=1\). Thus the degree multiset is \(\{3,3,2,1,1,1,1\}\). In \(H\), \(p\) and \(q\) each have degree \(3\), \(r\) has degree \(2\), and \(s,t,u,v\) each have degree \(1\). Its degree multiset is also \(\{3,3,2,1,1,1,1\}\).
Neither graph contains a cycle. In \(G\), vertices \(c,d,e,g\) have degree \(1\), so none can lie on a cycle; the remaining vertices \(a,b,f\) have only the edges \(ab,bf\) between them. In \(H\), the degree-\(1\) vertices \(s,t,u,v\) cannot lie on a cycle, and the remaining vertices \(p,r,q\) have only the edges \(pr,rq\) between them. Consequently \(c_k(G)=c_k(H)=0\) for every \(k\ge3\).
However, the two degree-\(3\) vertices of \(G\), namely \(a,b\), are adjacent, while the two degree-\(3\) vertices of \(H\), namely \(p,q\), are not adjacent. An isomorphism must preserve degrees and adjacency, so it would have to send the two degree-\(3\) vertices of \(G\) to the two degree-\(3\) vertices of \(H\) and preserve whether they are adjacent. That is impossible. Hence \(G\) and \(H\) are not isomorphic.
Check: The degree sums are \(3+3+2+1+1+1+1=12=2\cdot6\) in both graphs. Also, each graph is connected by its listed edges: in \(G\), every vertex connects to \(a\) or \(b\) through the displayed edges; in \(H\), every vertex connects to \(p\) or \(q\). The cycle-free checks above therefore account for every possible cycle, not just cycles in one component.
A Practical Candidate-Testing Method
For a pair of graphs, use invariants as filters rather than as a certificate of isomorphism. The order of the tests can be adjusted, but a compact procedure is:
If \(|V(G)|\ne|V(H)|\), the graphs cannot be isomorphic.
If \(|E(G)|\ne|E(H)|\), reject the candidate pair.
Sort the degrees, retaining every repetition. Any difference rules out isomorphism.
Where useful, count cycles by length. A difference for even one length rules out isomorphism.
If all these tests match, further structural comparison is still needed.
The logic of each rejection is the contrapositive of the invariance theorem: if the graphs were isomorphic, the tested quantities would agree. But the theorem has only established that isomorphism implies agreement, not that agreement implies isomorphism. The last worked example makes this distinction concrete.
Common Pitfall
Wrong conclusion: “Both graphs have seven vertices, six edges, degree multiset \(\{3,3,2,1,1,1,1\}\), and no cycles, so they are isomorphic.” This calculation correctly compares the listed invariants but draws a conclusion they do not justify. In the final example, the degree-\(3\) vertices are adjacent in \(G\) and nonadjacent in \(H\). The correction is to use matching invariants only to retain a pair as a candidate; to prove isomorphism, one must still establish that the adjacency structure matches.
Check Your Understanding
For each question, distinguish a test that can rule out isomorphism from evidence that would actually establish it.
- Can two isomorphic graphs have different degree multisets? Justify your answer from the definition of isomorphism.
- Suppose two graphs have the same order, size and degree multiset, but different numbers of 4-cycles. What can you conclude?
- For the last worked example, state the degree multiset and cycle count \(c_k\) for each graph.
- Why does agreement on \(c_3,c_4,\ldots,c_n\) not guarantee isomorphism, even when order, size and degrees also agree?
- Give the first invariant you would check for graphs with different numbers of vertices, and explain why that test is decisive.