Planar Graphs and Isomorphisms (AQA A-Level Further Maths): Revision Notes

Planar Graphs and Isomorphisms

Introduction to graph representation

Before exploring planar graphs and isomorphisms, it's important to understand how graphs can be described and represented mathematically.

A graph consists of points called vertices connected by lines called edges. When describing a specific graph, you can use two methods: listing the vertex set and edge set, or constructing an adjacency matrix.

For the graph shown above, you can describe it by stating the vertex set {A, B, C, D, E} together with the edge set {AB, AC, AD, BD, CD, DE} of the graph.

Adjacency matrices

An adjacency matrix provides a numerical way to represent a graph. This shows the number of connections between each pair of vertices in the graph. An undirected loop at a vertex would be recorded as 2 in the matrix.

To construct an adjacency matrix, create a table where both rows and columns are labelled with the vertex names. Each cell contains the number of edges connecting the corresponding pair of vertices. For simple graphs (those without loops or multiple edges), the adjacency matrix contains only 0s and 1s.

The complement of a graph

The complement of a simple graph G is denoted by G' and contains the same vertices as G but includes only the edges that are NOT in the original graph G.

To understand this concept, consider that if graph G has certain edges connecting its vertices, then G' has all the OTHER possible edges between those same vertices.

Finding the complement using adjacency matrices

There's a straightforward method to find the adjacency matrix for G' from the adjacency matrix of G:

The leading diagonal stays as 0s because the complement shouldn't introduce loops where the original graph didn't have them.

Relationship with complete graphs

An important property of complements is their relationship with complete graphs. When you combine a simple graph G with its complement G', you obtain the complete graph $K_n$, where n is the number of vertices.

A complete graph $K_n$ with n vertices is one where every possible pair of vertices is connected by an edge. The complete graph $K_n$ has $\frac{n(n-1)}{2}$ edges.

For example, if a simple graph has 5 vertices, then G combined with G' gives $K_5$. This makes sense because together, G and G' include every possible edge between the 5 vertices exactly once.

Isomorphic graphs

Two graphs $G_1$ and $G_2$ are isomorphic if they have the same structure. This means that even though the graphs may look different when drawn, they are essentially the same graph with vertices potentially relabelled or repositioned.

More formally, graphs are isomorphic if there's a one-to-one correspondence between their vertices such that if an edge joins two vertices in $G_1$, then there's an edge between the corresponding vertices in $G_2$, and vice versa.

Testing for isomorphism

To determine whether two graphs are isomorphic, you need to establish a vertex correspondence and verify that the edge patterns match. Here are several approaches:

Method 1: Compare adjacency matrices

If you list corresponding vertices in the same order, the adjacency matrices will be identical for isomorphic graphs.

In this example, if you pair vertices {A, B, C, D} with vertices {Q, S, P, T} in that specific order, then the edges {AC, AD, BC, BD, CD, DE} from the first graph correspond to {QP, QT, SP, ST, PT, TR} in the second graph. The adjacency matrices, when arranged with corresponding vertices in the same positions, are identical.

Method 2: Use degree sequences

The degree sequence lists the degrees of all vertices in the graph. For two graphs to be isomorphic, they must have the same degree sequence. However, having the same degree sequence does NOT guarantee isomorphism – it's a necessary but not sufficient condition.

Planar graphs

A graph is planar if it can be drawn in a plane without any edges crossing, except at vertices. This is a fundamental concept in graph theory with important applications in circuit design, map drawing, and network planning.

When a planar graph is drawn without edge crossings, it divides the plane into regions called faces. A face is a region bounded by edges in the plane drawing. Remember to count the "infinite face" – the unbounded region surrounding the entire graph.

Euler's formula

For any simple, connected planar graph drawn in the plane with V vertices, E edges, and F faces (including the infinite face):

$V + F - E = 2$

This is Euler's formula and is a key tool for determining whether a graph is planar.

Corollaries of Euler's formula

Several useful inequalities follow from Euler's formula for graphs with no degree 1 vertices, loops, or multiple edges:

For simple connected planar graphs:

If every edge borders exactly two faces, and every face has at least three edges, then:

$2E \geq 3F$

Substituting this into Euler's formula gives: $E \leq 3V - 6$

For a graph with $V = 5$ and $E = 10$ edges, we'd need $10 \leq 3(5) - 6 = 9$, which is false. Therefore, K₅ is non-planar.

For bipartite graphs:

In a bipartite graph, every face must have at least four edges (because bipartite graphs have no triangles), giving:

$2E \geq 4F$

This leads to: $E \leq 2V - 4$

For $K_{3,3}$ with $V = 6$ and $E = 9$: we'd need $9 \leq 2(6) - 4 = 8$, which is false. Therefore, K₃,₃ is non-planar.

Kuratowski's theorem

While Euler's formula provides necessary conditions for planarity, Kuratowski's theorem gives a complete characterization:

Recall that a subdivision of a graph is formed by adding vertices of degree 2 along existing edges. This theorem provides a definitive test for non-planarity.

Worked example: Using Kuratowski's theorem

Worked example: Complete solution with complement and isomorphism