Difficulty: Intermediate to Advanced | Prerequisites: Basic graph theory (vertices, edges, degree), probability fundamentals, Bayes' theorem
Graph isomorphism asks whether two graphs are "the same" up to relabelling their vertices. It is one of the few natural problems whose exact computational complexity is still unresolved: it sits somewhere between P and NP-complete, and nobody has proved it belongs to either class.
Interactive proofs take this further. Instead of a static certificate, you have a dialogue between a prover (Merlin) and a verifier (Arthur). The graph non-isomorphism protocol shows that even problems without obvious short proofs can be verified through clever use of randomness. These ideas underpin zero-knowledge proofs and modern cryptographic protocols. You should already be comfortable with basic graph definitions and elementary probability before tackling this material.
Two graphs are isomorphic if one can be turned into the other by renaming vertices. You can disprove isomorphism by finding an invariant (like the degree sequence) that differs between them. To prove non-isomorphism interactively, the prover exploits the fact that non-isomorphic graphs produce distinguishable random relabellings, while isomorphic graphs do not.
Graph isomorphism
A bijection f : V₁ → V₂ between two graphs' vertex sets such that (u, v) is an edge in G₁ if and only if (f(u), f(v)) is an edge in G₂. In simple terms, the two graphs have exactly the same structure; only the vertex names differ.
Degree sequence
The sorted list of vertex degrees in a graph. If two graphs have different degree sequences, they cannot be isomorphic. Think of it as a fingerprint: matching fingerprints do not prove identity, but mismatched ones rule it out.
Graph invariant
Any property of a graph that is preserved under isomorphism (e.g. number of vertices, number of edges, degree sequence, number of triangles). Useful for quickly ruling out isomorphism.
Interactive proof
A protocol where a computationally unbounded prover (Merlin) tries to convince a probabilistic polynomial-time verifier (Arthur) of a claim. The verifier uses randomness and can reject a dishonest prover with high probability.
Arthur-Merlin protocol
A specific kind of interactive proof where the verifier's randomness is public (Arthur's coin flips are visible to Merlin). The graph non-isomorphism protocol in this homework is an Arthur-Merlin protocol.
Soundness
The guarantee that a dishonest prover cannot fool the verifier (except with small probability). In the graph non-isomorphism protocol, if the graphs are actually isomorphic, the prover can fool the verifier with probability at most 1/2^k.
Completeness
The guarantee that an honest prover can always convince the verifier. If the graphs truly are non-isomorphic, the prover can always identify which graph was relabelled.
Vertex relabelling (random permutation)
Applying a random bijection to the vertex names of a graph. The resulting graph is isomorphic to the original by construction.
An isomorphism between G₁ = (V₁, E₁) and G₂ = (V₂, E₂) is a bijection f : V₁ → V₂ such that (u, v) ∈ E₁ if and only if (f(u), f(v)) ∈ E₂. Every edge is preserved and every non-edge is preserved.
A necessary (but not sufficient) condition for isomorphism: both graphs must have the same degree sequence. If one graph has a vertex of degree 5 and the other does not, no bijection can map the first to the second, because isomorphisms preserve vertex degree.
Two graphs G₁ and G₂, each with 9 vertices labelled A through I, were given.
Degree counts for G₁: A = 3, B = 2, C = 2, D = 1, E = 1, F = 5, G = 2, H = 4, I = 2.
Degree counts for G₂: A = 1, B = 2, C = 4, D = 2, E = 2, F = 1, G = 2, H = 4, I = 4.
G₁'s sorted degree sequence: {1, 1, 2, 2, 2, 2, 3, 4, 5}.
G₂'s sorted degree sequence: {1, 1, 2, 2, 2, 2, 4, 4, 4}.
The sequences differ. In particular, G₁ has a vertex of degree 5 (vertex F) and a vertex of degree 3; G₂ has no vertex of degree 5 and no vertex of degree 3. Therefore G₁ and G₂ are not isomorphic.
The degree of a vertex is an invariant under isomorphism: if f maps u to v, then u and v must have the same degree. So the multiset of degrees must be identical. A single mismatch in the degree sequence is a valid proof of non-isomorphism.
Matching degree sequences do not prove isomorphism. There exist non-isomorphic graphs with identical degree sequences (for example, certain pairs of 4-regular graphs on the same number of vertices). To prove isomorphism, you must exhibit the bijection itself.
Input: Two graphs G₁, G₂ and a number of rounds k.
Goal: Merlin (prover) wants to convince Arthur (verifier) that G₁ and G₂ are not isomorphic.
Each round:
Arthur picks i = 1 or 2 uniformly at random, then randomly relabels the vertices of G_i to produce H.
Arthur sends H to Merlin.
Merlin sends back a guess c (either 1 or 2).
If c ≠ i, Arthur rejects immediately.
After k rounds with no rejection, Arthur accepts.
If the graphs are genuinely non-isomorphic, a computationally unbounded Merlin can always tell which graph H came from. A random relabelling of G₁ is always isomorphic to G₁ (and not to G₂), and vice versa. So Merlin simply checks whether H is isomorphic to G₁ or G₂ and answers correctly every time. Arthur accepts with probability 1.
Part (a): The relabelling distribution is identical.
When G₁ ≅ G₂, the set of all possible relabellings of G₁ is the same as the set of all possible relabellings of G₂ (they are isomorphic, so they share the same isomorphism class). For any particular graph H₀, Pr[H = H₀ | i = 1] = Pr[H = H₀ | i = 2] = 1/y, where y is the number of distinct relabellings.
Part (b): Merlin gains no information from H.
By Bayes' theorem:
Pr[i = 1 | H = H₀] = Pr[H = H₀ | i = 1] × Pr[i = 1] / Pr[H = H₀]
Since Pr[H = H₀ | i = 1] = Pr[H = H₀] (from part a), this simplifies to Pr[i = 1 | H = H₀] = Pr[i = 1] = 1/2.
Knowing H gives Merlin no information about i. He is guessing a fair coin. In each round, his probability of guessing correctly is at most 1/2. Over k independent rounds, the probability he guesses correctly every time is at most (1/2)^k = 1/2^k.
The protocol works because non-isomorphic graphs produce distinguishable distributions when relabelled, while isomorphic graphs produce identical distributions. This asymmetry is what the verifier exploits.
Isomorphism condition:
f : V₁ → V₂ is an isomorphism iff for all u, v ∈ V₁: (u, v) ∈ E₁ ⟺ (f(u), f(v)) ∈ E₂.
Soundness bound for graph non-isomorphism protocol:
Pr[Arthur accepts | G₁ ≅ G₂] ≤ (1/2)^k, where k is the number of rounds.
Bayes' theorem (as used in the soundness proof):
Pr[i = 1 | H = H₀] = Pr[H = H₀ | i = 1] × Pr[i = 1] / Pr[H = H₀].
Graph isomorphism testing appears in chemistry (comparing molecular structures), network analysis (finding equivalent subnetworks), and compiler optimisation (detecting equivalent code patterns). Interactive proofs are the theoretical foundation of zero-knowledge proofs, which power privacy-preserving authentication systems and certain blockchain protocols. The idea that you can prove something without revealing how you know it has practical applications in identity verification and secure computation.
Students often think matching degree sequences prove isomorphism. They do not. Matching degree sequences are necessary but not sufficient. You can have two non-isomorphic graphs with identical degree sequences.
Students confuse the roles: Merlin is the prover (unbounded computation), Arthur is the verifier (polynomial time, uses randomness). Arthur does not need to solve the problem; he only needs to check Merlin's claim.
A frequent mistake is thinking that if Merlin is "smart enough," he can fool Arthur even when the graphs are isomorphic. The soundness proof shows this is impossible: the information simply is not there. The distributions are identical, so no strategy helps.
Students sometimes believe the protocol proves isomorphism. It proves non-isomorphism. The honest prover succeeds when the graphs are not isomorphic.
⚠️ Expect to be asked to determine whether two graphs are isomorphic and justify your answer. The degree-sequence check is the first thing to try; know how to count degrees quickly.
⚠️ The graph non-isomorphism protocol is a classic exam topic. Be ready to explain the protocol step by step, and to prove both completeness and soundness.
⚠️ The Bayes' theorem calculation in the soundness proof is a likely exam question. Make sure you can derive Pr[i = 1 | H = H₀] = 1/2 from first principles when G₁ ≅ G₂.
⚠️ Know the distinction between necessary and sufficient conditions for isomorphism. Be able to name an invariant that is necessary but not sufficient (degree sequence) and explain why.
True or false: If two graphs have the same number of edges and vertices, they must be isomorphic. (False: they could have different degree sequences or different structures.)
Fill in the blank: In the graph non-isomorphism protocol, Arthur's probability of being fooled over k rounds is at most ______. (1/2^k)
True or false: The graph non-isomorphism protocol proves that two graphs are isomorphic. (False: it proves they are non-isomorphic.)
Fill in the blank: An isomorphism is a ______ between vertex sets that preserves edges. (bijection)
True or false: When G₁ ≅ G₂, seeing the relabelled graph H tells Merlin which graph Arthur chose. (False: the distributions are identical, so H gives no information.)
Q: Two graphs both have 8 vertices, 12 edges, and degree sequence {2, 2, 3, 3, 3, 3, 4, 4}. Are they necessarily isomorphic?
A: No. Matching degree sequences are a necessary condition but not sufficient. You would need to find an explicit bijection or use a more refined invariant (e.g. counting triangles or checking neighbourhood structures) to determine isomorphism.
Q: In the graph non-isomorphism protocol, what happens if the graphs really are non-isomorphic and Merlin is honest?
A: Merlin can always identify which graph H came from (since the isomorphism classes of G₁ and G₂ are distinct). He answers correctly every round, and Arthur accepts with probability 1. This is the completeness property.
Q: Suppose G₁ ≅ G₂. Merlin claims they are not isomorphic and runs the protocol for k = 10 rounds. What is the maximum probability Arthur accepts?
A: At most (1/2)^{10} = 1/1024. In each round, Merlin is guessing a fair coin, because the distribution of H is identical regardless of whether Arthur chose G₁ or G₂.
Q: Why does the protocol use random relabelling rather than just sending one of the graphs directly?
A: Random relabelling is what makes the two distributions (from G₁ vs G₂) either identical (when isomorphic) or distinguishable (when not). Sending the graph without relabelling would trivially reveal which graph was chosen.
The interactive proof framework connects to complexity classes IP and AM, which generalise NP by allowing interaction and randomness. Graph isomorphism is closely related to the hidden subgroup problem in quantum computing, which is why it received renewed attention after Babai's 2015 quasi-polynomial algorithm. The secret sharing material from the same homework uses the same underlying theme: randomness as a tool for hiding and revealing information in a controlled way.
Graph isomorphism, graph non-isomorphism, interactive proof, Arthur-Merlin protocol, zero-knowledge proof, degree sequence, graph invariant, vertex bijection, soundness, completeness, random relabelling, vertex permutation, Bayes' theorem, IP complexity class, AM complexity class, EECS 376, foundations of computer science, University of Michigan