Isomorphism of graphsAQA A-Level Further Maths: Revision notes

Two graphs are isomorphic if they have the same structure, even if they are drawn differently or their vertices are labelled differently. Formally, $G$ and $H$ are isomorphic if there is a one-to-one correspondence $f$ between their vertices (a bijection) 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 called an isomorphism. So an isomorphism maps edges to edges and non-edges to non-edges, and every edge of $H$ is the image of an edge of $G$.

If $G$ and $H$ are isomorphic then they must have:

• the same number of vertices;
• the same number of edges;
• the same degree sequence (the list of degrees in order of size), because the isomorphism maps each vertex to one of equal degree;
• the same cycle structure, for example the same number of triangles, and both connected or both not, both bipartite or both not. These are necessary conditions. If any fails, the graphs are not isomorphic. If all hold, the graphs may be isomorphic: they are not sufficient.

To prove isomorphism, construct the mapping and check every edge.

1. Check the necessary conditions first.
2. Use features that are unique to match vertices, for example the only vertex of degree 3, or the only vertex of degree 1.
3. Extend the matching using adjacencies, and write the mapping out in full.
4. Show that every edge of one graph maps to an edge of the other, and that the two graphs have the same number of edges (so no edge is left over). Example: $P$ has edges $AB, BC, CD, DE, EA, AC$; $Q$ has edges $12, 23, 34, 45, 51, 25$. Take $A\to2$, $B\to1$, $C\to5$, $D\to4$, $E\to3$. The edges map to $21, 15, 54, 43, 32, 25$, all edges of $Q$, and both graphs have 6 edges.

To prove graphs are not isomorphic you need only one property 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 a cycle of a given length in one but not the other, being bipartite, or being connected. Example: $K_{3,3}$ and the triangular prism both have 6 vertices, 9 edges and all degrees 3. The prism contains a triangle but $K_{3,3}$ is bipartite and has none, so they are not isomorphic.

Isomorphic graphs have the same adjacency matrix once the vertices of one are relisted in the order given by the isomorphism. Different orderings of the vertices of one graph give different matrices, which is why two matrices may look different for isomorphic graphs. Quick checks from the matrices: 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. Example: a graph with matrix rows $(0,1,1,0)$, $(1,0,1,1)$, $(1,1,0,0)$, $(0,1,0,0)$ has degrees $2,3,2,1$ and 4 edges.