DA7 - Graph isomorphism

DA7 - Graph isomorphism

Two graph drawings can look different while describing exactly the same pattern of connections. Learn to rule out false matches using properties that relabelling preserves, and to prove a match by giving a complete correspondence of vertices. You will distinguish evidence that suggests a match from an argument that establishes it.

Properties preserved by isomorphism

Can a triangle with a point inside it and a square with both diagonals represent the same graph? The shape alone cannot settle this: we need to compare connections.

Two graphs are isomorphic when there is a one-to-one correspondence between their vertices preserving adjacency in both directions. More formally, a bijection f:V(G)→V(H)f:V(G)\to V(H) must satisfy

uv∈E(G)⟺f(u)f(v)∈E(H)uv\in E(G)\quad\Longleftrightarrow\quad f(u)f(v)\in E(H)

for each pair of vertices. A bijection uses every vertex exactly once. For graphs with multiple edges, loops or directions, their numbers and directions must also be preserved; the examples here are simple undirected graphs.

An invariant is a property unchanged by an isomorphism. Vertex count, edge count, sorted degree list, number of connected components and cycle lengths are invariants. Neighbourhood structure is preserved too: a degree-3 vertex adjacent to three degree-2 vertices must map to a vertex with the same arrangement. An isomorphism changes names and positions, not these relationships.

To disprove isomorphism, one differing invariant is enough. Equal invariants are useful filters, but generally do not prove a match: different graphs can share several or even all of the basic counts you have checked.

Worked example 1: a degree obstruction

Question. G is the path A–B–C–D–E. H has vertices P, Q, R, S, T and edges PQ, PR, PS, PT. Determine whether they are isomorphic.

Plan. Compare degrees after checking their common vertex and edge counts.

Both have five vertices and four edges. However,

G: (2,2,2,1,1),H: (4,1,1,1,1)\text{G: }(2,2,2,1,1),\qquad \text{H: }(4,1,1,1,1)

H has a degree-4 vertex and G has none.

Answer. They are not isomorphic, because degrees must be preserved.

Check. G's maximum degree is 2 whereas H's is 4. Relabelling cannot supply a candidate image for P.

Now compare graphs where every degree agrees. A more local invariant must do the work.

Worked example 2: equal degrees, different cycles

Question. G consists of triangles ABC and DEF together with edges AD, BE, CF. H is K3,3K_{3,3}. Are they isomorphic?

Plan. Compare counts, then test for a triangle.

Both graphs have six vertices, nine edges and six vertices of degree 3. But G contains triangle A–B–C–A. H is bipartite, so every cycle alternates groups and has even length; it has no triangle.

Answer. They are not isomorphic: the existence of a 3-cycle is an invariant they do not share.

Check. The triangle's three mutually adjacent vertices would have to map to three mutually adjacent vertices in H. Any three vertices in two groups include two in the same group, which cannot be adjacent.

The second example shows why a degree list is a starting test, rather than a universal fingerprint. Count an invariant accurately, state the difference, then connect it explicitly to the conclusion.

Watch out

A matching degree list does not prove isomorphism. A differing degree list does disprove it. The same one-way logic applies to matching edge counts and component counts.

Find one decisive invariant in a new pair.

Proving a vertex correspondence

A proposed matching becomes a proof only when it is a bijection and it preserves all the required edges and non-edges.

Start with vertices whose degrees or neighbourhoods identify their possible partners, then work outwards. Once you have a candidate, write the whole correspondence. For a simple graph, listing every image edge can verify adjacency. If the bijection maps all edges to edges and both graphs have the same number of edges, no target edge is left over, so non-adjacency is preserved too. Without the equal-edge-count check, preserving just some edges is insufficient.

Worked example 3: using distinctive degrees

Question. G has edges AB, BC, CA, CD. H has edges PR, RQ, QP, QS. Find an isomorphism.

Plan. Match the unique degree-3 and degree-1 vertices, then match the remaining triangle vertices.

C has degree 3 and D degree 1, so choose C mapped to Q and D to S. A and B both have degree 2; choose A mapped to P and B to R. The complete map is

A↦P,B↦R,C↦Q,D↦SA\mapsto P,\quad B\mapsto R,\quad C\mapsto Q,\quad D\mapsto S

Its edge images are

AB↦PR,BC↦RQ,CA↦QP,CD↦QSAB\mapsto PR,\quad BC\mapsto RQ,\quad CA\mapsto QP,\quad CD\mapsto QS

These are precisely H's four edges, and the four target vertices are all used once.

Answer. The displayed bijection is an isomorphism.

Check. G's missing pairs AD and BD map to PS and RS, both absent in H. This checks non-adjacency directly as well.

Keep the same triangles and lengthen each pendant path by one edge. The old map should extend, rather than be rebuilt without reason.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account