Recipe

Determine whether two graphs are isomorphic

Use when: you're given two graphs G and H, possibly with entirely different vertex labels, and asked whether they're isomorphic

Goal: either a working bijection proving G is isomorphic to H, or one disagreeing invariant proving they aren't

Taught in Graph isomorphism, revisited

1. 1

   Count |V(G)| against |V(H)|, and |E(G)| against |E(H)|. These are the two cheapest checks available.

   Example

   G a path on \{1,2,3,4\} has order 4, size 3. H on \{W,X,Y,Z\} with edges \{WX,XY,XZ\} also has order 4, size 3, so this check alone doesn't decide anything yet.

   • either count disagrees — not isomorphic, stop here
   • both counts agree — continue to Step 2, though isomorphism is still unproven

   Why: an isomorphism is a bijection on vertex sets that matches edges exactly, so it forces both graphs to share the same vertex count and the same edge count.

2. 2

   List each graph's degree sequence as a sorted multiset, ignoring which vertex has which degree, and compare the two lists.

   Example

   For the same G and H: \deg(1)=1,\deg(2)=2,\deg(3)=2,\deg(4)=1 gives (2,2,1,1); \deg(W)=1,\deg(X)=3,\deg(Y)=1,\deg(Z)=1 gives (3,1,1,1). These multisets disagree, so G and H are not isomorphic.

   • the sequences disagree — not isomorphic, stop here
   • the sequences agree — continue to Step 3, though isomorphism is still unproven

   Why: relabeling a vertex can never change how many edges attach to it, only which vertex owns that count, so the sequence has to match exactly as a multiset.

3. 3

   Compare something the earlier checks might miss, most commonly connectedness: does every vertex reach every other one in each graph?

   Example

   X is a single 6-cycle (one connected piece). Y is two separate triangles with no edge between them (two pieces). Order, size, and degree sequence all match, but X is connected and Y is not, so they aren't isomorphic.

   • the two graphs disagree on connectedness — not isomorphic, stop here
   • both graphs agree — continue to Step 4, though isomorphism is still unproven

   Why: an isomorphism carries a path in G to a path in H, so it must preserve connectedness exactly the way it preserves an edge count.

4. 4

   Propose a vertex correspondence \varphi, then check that every edge of G maps to an edge of H, and that no edge of H is left unmatched.

   Example

   G has V(G)=\{1,2,3\}, E(G)=\{\{1,2\},\{2,3\},\{1,3\}\}; H has V(H)=\{X,Y,Z\}, E(H)=\{\{X,Y\},\{Y,Z\},\{X,Z\}\}. Try \varphi(1)=X,\varphi(2)=Y,\varphi(3)=Z: all three G-edges land on H-edges, and H has exactly three edges, so nothing is left unmatched.

   Why: matching invariants only ever narrows the search down, and only an actual working bijection, or a proof that none exists, settles isomorphism for certain.