Proof of the five colour theorem by Kempe chains

Proof

We argue by induction on the number $N$ of vertices. We show that every finite planar graph $G$ is $5$-colourable, which means $\chi(G) \le 5$ by the definition of the chromatic number.

Base case.

1. If $N \le 5$, give the vertices pairwise distinct colours from $\set{1, \dots, 5}$. This is a colouring.

A vertex of small degree.

2. Let $G$ be a finite planar graph with $N \ge 6$ vertices. Graphs are simple here, and every subgraph of $G$ is planar, by erasing part of a drawing of $G$.
3. We claim that $G$ has a vertex of degree at most $5$. Let $H$ be the subgraph induced by a connected component of $G$, with $m$ vertices. Each vertex of $H$ has the same degree in $H$ as in $G$.
4. If $m \le 2$, each vertex of $H$ has degree at most $1$.
5. If $m \ge 3$, then $H$ is a connected simple planar graph. By the edge bound for planar graphs, $H$ has at most $3m - 6$ edges.
6. By the handshaking lemma, the degrees in $H$ sum to at most $2(3m - 6) = 6m - 12 < 6m$. So some vertex of $H$ has degree at most $5$. This proves the claim.

Induction step.

7. Let $x$ be a vertex of $G$ with degree at most $5$. Let $G' = G - x$ be the graph obtained by deleting $x$ and its edges. It is planar and has $N - 1$ vertices.
8. By the induction hypothesis, $G'$ has a colouring $c$ with colours in $\set{1, \dots, 5}$.
9. If the neighbours of $x$ use at most $4$ colours under $c$, give $x$ a colour that they do not use. This extends $c$ to a colouring of $G$.
10. Otherwise $x$ has exactly $5$ neighbours with $5$ distinct colours. Fix a drawing of $G$ with no crossings. Name the neighbours $y_1, \dots, y_5$ in the cyclic order in which their edges leave $x$. Rename the colours so that $c(y_i) = i$.

Kempe chains.

11. For colours $i \ne j$, let $G_{ij}$ be the subgraph induced in $G'$ by the vertices of colour $i$ or $j$.
12. Let $K$ be a connected component of $G_{ij}$. Swapping the colours $i$ and $j$ on the vertices of $K$ gives a new colouring of $G'$. We check each edge $pq$ of $G'$.
13. If $p, q \in K$, they had the two different colours $i$ and $j$, and after the swap they still have different colours. If $p, q \notin K$, nothing changes at $pq$.
14. Let $p \in K$ and $q \notin K$. If $c(q) \in \set{i, j}$, then $q$ is a vertex of $G_{ij}$ adjacent to $p$, so $q \in K$, which is false. So $c(q) \notin \set{i, j}$, while $p$ still has colour $i$ or $j$. The colours differ.

Case A: $y_1$ and $y_3$ are in different components of $G_{13}$.

15. Swap the colours $1$ and $3$ on the component $K$ of $G_{13}$ that contains $y_1$. By Step 12, this gives a colouring of $G'$.
16. Now $y_1$ has colour $3$, and $y_3 \notin K$ keeps colour $3$. The vertices $y_2, y_4, y_5$ have colours $2, 4, 5$, so they are not in $G_{13}$ and keep their colours.
17. No neighbour of $x$ has colour $1$ now. Give $x$ colour $1$ to get a colouring of $G$.

Case B: $y_1$ and $y_3$ are in the same component of $G_{13}$.

18. Then there is a path $P$ from $y_1$ to $y_3$ in $G_{13}$. All its vertices have colour $1$ or $3$, so $P$ avoids $x$, $y_2$ and $y_4$.
19. Adding $x$ and the edges $x y_1$ and $x y_3$ to $P$ gives a cycle $C$ of $G$. Its drawing is a closed curve without self-intersections, since edges meet only at common ends.
20. By the Jordan curve theorem, the complement of $C$ in the plane has exactly two connected components, the inside and the outside.
21. Near $x$, the curve $C$ consists of the edges $x y_1$ and $x y_3$. The edges $x y_2$ and $x y_4$ leave $x$ into the two different angles between $x y_1$ and $x y_3$, by the cyclic order of Step 10. So they start on different sides of $C$.
22. The edges $x y_2$ and $x y_4$ meet $C$ only at $x$, and $y_2, y_4$ are not on $C$. So $y_2$ and $y_4$ lie in different components of the complement of $C$.
23. Suppose there were a path $Q$ from $y_2$ to $y_4$ in $G_{24}$. Its drawing is a connected curve from one component of the complement of $C$ to the other. So it meets $C$.
24. Edges meet only at common ends, so $Q$ and $C$ share a vertex. But the vertices of $Q$ have colours $2$ or $4$, while those of $C$ are $x$ or have colours $1$ or $3$. This is impossible.
25. Hence $y_2$ and $y_4$ are in different components of $G_{24}$. As in Steps 15 to 17, swap colours $2$ and $4$ on the component that contains $y_2$, and give $x$ colour $2$.

Conclusion.

26. In all cases $G$ has a colouring with $5$ colours. By induction, every finite planar graph $G$ satisfies $\chi(G) \le 5$.