Questions: Graph Isomorphism

Question 1

Graphs G and H have the same vertex count, edge count, and degree sequence [3, 2, 2, 1]. What can you conclude?

• A. G and H are isomorphic, since they share all these invariants
• B. G and H are not isomorphic, since no further checks are needed once three invariants match
• C. G and H may or may not be isomorphic — matching invariants is necessary but not sufficient
• D. G and H are isomorphic only if they are drawn the same way

Answer: (C)

Matching invariants (vertex count, edge count, degree sequence) rules out non-isomorphism only when they *differ*. When they match, you cannot yet conclude isomorphism — you must still exhibit an explicit edge-preserving bijection. Option A is the classic misconception: necessary conditions are not sufficient. Option D confuses graph drawings with graph structure — two isomorphic graphs can look completely different when drawn.

Question 2

You want to prove two graphs are NOT isomorphic as efficiently as possible. Which strategy is best?

• A. Enumerate all n! possible bijections between their vertex sets and verify none preserve edges
• B. Apply cheap invariants first (degree sequence, girth, triangle count); stop as soon as one differs
• C. Draw both graphs and observe whether they look different
• D. Check whether both graphs are connected

Answer: (B)

Disproving isomorphism only requires finding one invariant that differs. Applying cheap invariants (degree sequence first, then girth, triangle count, etc.) prunes the search immediately — if degree sequences differ, no bijection can exist, and you're done. Option A (enumerating all n! bijections) is what you'd do to prove isomorphism, not disprove it, and is computationally infeasible for large n. Option C is the fundamental misconception: graph drawings are arbitrary and visually different graphs may be isomorphic.

Question 3

Two graphs that are drawn differently on paper can seldom be isomorphic.

• T. True
• F. False

Answer: False

This is the most common misconception in graph isomorphism. A graph can be drawn in infinitely many ways — vertex positions and edge curves are arbitrary visual choices, not part of the mathematical structure. The same graph drawn as a neat square with diagonals and as a tangled mess of crossing lines is still the same graph. Isomorphism is about whether an edge-preserving bijection exists between vertex sets, not about visual similarity.

Question 4

The degree sequence of a graph is preserved under any isomorphism — if two graphs are isomorphic, their degree sequences must be identical.

• T. True
• F. False

Answer: True

Degree is a structural property: the degree of a vertex is the number of edges incident to it. Any isomorphism maps vertices to vertices in an edge-preserving way, so each vertex's degree must be the same as its image's degree. This makes degree sequence one of the most useful and cheapest invariants to check. Note, however, that matching degree sequences does not guarantee isomorphism — it is a necessary, not sufficient, condition.

Question 5

Why is proving two graphs are isomorphic harder than proving they are non-isomorphic?

Model answer: To prove non-isomorphism, you only need to find a single invariant that differs — one mismatch is enough to rule out any bijection. To prove isomorphism, you must exhibit an explicit edge-preserving bijection and verify every edge is mapped correctly. There is no shortcut: you cannot simply confirm invariants match and declare success. For n vertices, there are n! possible bijections to consider, which grows impossibly large even for moderate n, making the constructive proof the difficult direction.

This asymmetry — that disproving is easy (find a counterexample invariant) while proving requires construction — is a general feature of existence proofs. It also explains why graph isomorphism is computationally hard: while invariant-checking can rule out most pairs quickly, the remaining 'pass' cases require expensive construction. The fact that graph isomorphism sits in computational limbo (not known to be in P or NP-complete) reflects exactly this asymmetry.