Isomorphism of graphs
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.
and are isomorphic if there is a one-to-one correspondence between their vertices (a bijection) such that and are adjacent in if and only if and are adjacent in . Such an is an isomorphism.
So an isomorphism maps edges to edges and non-edges to non-edges, and every edge of is the image of an edge of .
- Isomorphism adjacent 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 and 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.
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
has degree sequence and has degree sequence . 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.
Worked example
has edges ; has edges . Show that they are isomorphic.
- 1
Both have 5 vertices and 6 edges. Degrees: in , and have degree 3 and have degree 2; in , and have degree 3 and have degree 2.
- 2
Match the degree-3 vertices: and . is adjacent to both and , as is to and , so .
- 3
Then (next to ) goes to and (next to ) goes to .
- 4
Map the edges: , , , , , . All are edges of .
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:
- number of vertices and number of edges;
- degree sequence;
- other structure: a triangle or cycle of a given length in one but not the other, being bipartite, or being connected.
and the triangular prism both have 6 vertices, 9 edges and all degrees 3. The prism contains a triangle but is bipartite and has none, so they are not isomorphic.
Which property can show that 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.
- Row sumsdegrees
- Sum of all entries number of edges
Worked example
A graph has adjacency matrix with rows , , , . Find its degrees and number of edges.
- 1
Row sums: .
- 2
Sum of all entries: .
- 3
Edges: .
Two graphs have different adjacency matrices. Can they still be isomorphic?
Try an exam question
Graph has degree sequence and graph has degree sequence . Both have vertices and edges. Show that and are not isomorphic.
[3 marks]
- [1]Both graphs have 6 vertices and 8 edges, so these do not distinguish them.
- [1]An isomorphism preserves the degree of each vertex, so isomorphic graphs have the same degree sequence.
- [1]The degree sequences differ ( has a vertex of degree 4), so and are not isomorphic.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Graph has 6 vertices and 7 edges. Can and be isomorphic?
1 mark, marked against the mark scheme
Graph has 6 vertices and 7 edges. Can and be isomorphic?
1 mark, marked against the mark scheme