Isomorphism of graphs

Isomorphism of graphs

Spec DA7 · AQA A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Two graphs are isomorphic if a one-to-one matching of vertices preserves adjacency.
  • Isomorphic graphs have the same number of vertices, edges, degree sequence and cycle structure.
  • These conditions are necessary but not sufficient: matching counts do not prove isomorphism.
  • To prove isomorphism, build the mapping and check every edge.
  • To disprove it, find one property that differs and say that isomorphisms preserve it.

What isomorphism means

Two graphs are isomorphic when they have the same structure, even if drawn differently or labelled differently.

GG and HH are isomorphic if there is a one-to-one correspondence ff between their vertices (a bijection) such that uu and vv are adjacent in GG if and only if f(u)f(u) and f(v)f(v) are adjacent in HH. Such an ff is an isomorphism.

So an isomorphism maps edges to edges and non-edges to non-edges, and every edge of HH is the image of an edge of GG.

ABCDPQRS
Two drawings of the same graph, a 4-cycle: A–B–C–D–A on the left, P–Q–R–S–P on the right. Adjacent vertices correspond, so they are isomorphic.
  • Isomorphism ffu,vu,v adjacent   ⟺  \iff f(u),f(v)f(u),f(v) adjacent

Two graphs have different vertex labels but a one-to-one matching of vertices that preserves adjacency. Are they isomorphic?

Necessary conditions

Isomorphic graphs must agree on vertices, edges, degrees and cycles, but agreeing does not prove they are isomorphic.

If GG and HH are isomorphic they must have the same number of vertices, the same number of edges and the same degree sequence (the degrees listed in order of size), because the isomorphism maps each vertex to one of equal degree. They must also share cycle structure, such as the number of triangles, and both be connected or not, both bipartite or not.

These are necessary conditions. If any fails, the graphs are not isomorphic. If all hold, they may be isomorphic.

ABCDEFPQRSTU
Same vertices (6), edges (6) and degree sequence (all 2), but not isomorphic: the first graph is connected, the second is two separate triangles

Must match

  • Number of vertices
  • Number of edges
  • Degree sequence
  • Triangles and other cycles
  • Connected, bipartite

What matching shows

  • Any difference proves the graphs are not isomorphic
  • All agreeing only means they might be isomorphic

GG has degree sequence 3,3,2,2,23,3,2,2,2 and HH has degree sequence 4,2,2,2,24,2,2,2,2. Both have 5 vertices and 6 edges. Are they isomorphic?

Proving graphs are isomorphic

Build a full vertex mapping and show that every edge of one graph maps to an edge of the other.

Check the necessary conditions first. Then use features that are unique to match vertices, for example the only vertex of degree 3 or the only vertex of degree 1. Extend the matching using adjacencies and write the mapping out in full.

Finally show that every edge of one graph maps to an edge of the other, and that the graphs have the same number of edges, so no edge is left over.

ABCDE12345
Graph PP (left, vertices AA to EE) and graph QQ (right, vertices 1 to 5).

Worked example

PP has edges AB,BC,CD,DE,EA,ACAB, BC, CD, DE, EA, AC; QQ has edges 12,23,34,45,51,2512, 23, 34, 45, 51, 25. Show that they are isomorphic.

Why do you start by matching vertices of the same degree?

Proving graphs are not isomorphic

Find one property that differs, and state that an isomorphism would preserve it.

You need only one invariant that differs, and you must say that an isomorphism preserves it. Compare in this order:

  1. number of vertices and number of edges;
  2. degree sequence;
  3. other structure: a triangle or cycle of a given length in one but not the other, being bipartite, or being connected.

K3,3K_{3,3} and the triangular prism both have 6 vertices, 9 edges and all degrees 3. The prism contains a triangle but K3,3K_{3,3} is bipartite and has none, so they are not isomorphic.

ABCDEF
Triangular prism: 6 vertices, 9 edges, all of degree 3.

Which property can show that K3,3K_{3,3} and the triangular prism are not isomorphic?

Adjacency matrices and isomorphism

Isomorphic graphs have the same adjacency matrix once their vertices are relisted in the order the isomorphism gives.

Different orderings of the vertices of one graph give different matrices, which is why two matrices may look different for isomorphic graphs. Relabelling the vertices can make them equal.

Quick checks from a matrix: the sum of all entries is twice the number of edges, and row sums give the degrees, so the degree sequence can be read off without drawing the graph.

ABCD
Edges AB, BC, BD and CD: the degrees (row sums) are A 1, B 3, C 2, D 2. They add to 8, which is 2 × 4 edges.
  • Row sumsdegrees
  • Sum of all entries2×2\times number of edges

Worked example

A graph has adjacency matrix with rows (0,1,1,0)(0,1,1,0), (1,0,1,1)(1,0,1,1), (1,1,0,0)(1,1,0,0), (0,1,0,0)(0,1,0,0). Find its degrees and number of edges.

Two graphs have different adjacency matrices. Can they still be isomorphic?

Try an exam question

Graph GG has degree sequence 3,3,3,3,2,23,3,3,3,2,2 and graph HH has degree sequence 4,3,3,2,2,24,3,3,2,2,2. Both have 66 vertices and 88 edges. Show that GG and HH are not isomorphic.

[3 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Graph HH has 6 vertices and 7 edges. Can GG and HH be isomorphic?

1 mark, marked against the mark scheme

Revision notes