Graph Isomorphism

Same graph up to relabeling — test it with degree-sequence invariants.

The idea

Graphs $G$ and $H$ are isomorphic, written $G \cong H$, if there is a bijection $f$ from the vertices of $G$ onto the vertices of $H$ such that $u$ and $v$ are adjacent in $G$ if and only if $f(u)$ and $f(v)$ are adjacent in $H$. Such an $f$ is an isomorphism. The "if and only if" works in both directions: an isomorphism carries edges to edges and non-edges to non-edges. Isomorphic graphs are the same graph up to renaming its vertices — a graph records only which pairs are joined, so redrawing it or relabeling it produces an isomorphic copy.

Testing the definition directly means searching for a bijection, and on $n$ vertices there are $n!$ candidates. The practical tool is an invariant: a quantity computed from a graph without reference to the names of its vertices, which therefore comes out equal for isomorphic graphs. The number of vertices, the number of edges, and the degree sequence — the list of vertex degrees written in decreasing order — are all invariants; an isomorphism pairs each vertex with one of the same degree. Two graphs that differ in any invariant are not isomorphic.

Ways to work on it

• Walkthrough. The isomorphism relation and the invariants that test it.
• Practice. Use the degree sequence to settle a pair of graphs.
• Hardest. Invariants tie — find the adjacency-preserving bijection, then count the automorphisms.

Not sure where to start? Take the ten-question placement test.