[proofplan] We induct on $|G|$. The base case $|G| \leq 5$ is immediate by assigning each vertex a distinct colour. For the inductive step we pick a vertex $x$ of degree at most $5$ (guaranteed in any planar graph by the fact that planar graphs have a vertex of degree at most $5$) and apply the inductive hypothesis to $G - x$ to obtain a $5$-colouring. If $\deg x \leq 4$ or if the five neighbours of $x$ do not consume all five colours, a free colour is immediately available. Otherwise, the five neighbours $x_1, \ldots, x_5$ of $x$ (arranged cyclically in the plane) use all five colours exactly once. We attempt a Kempe-chain argument on the pair of colour classes $\{1, 3\}$: if no $\{1,3\}$-coloured path connects $x_1$ to $x_3$ in $G - x$, swapping colours $1$ and $3$ on the component of $x_1$ frees colour $1$ for $x$. Symmetrically for $\{2, 4\}$. If both Kempe chains exist — a $\{1,3\}$-path from $x_1$ to $x_3$ and a $\{2,4\}$-path from $x_2$ to $x_4$ — the planar embedding of $G$ forces the two paths to cross, but a crossing vertex would need two different colours simultaneously, giving a contradiction. Hence at least one Kempe swap always succeeds. [/proofplan] [step:Set up induction on $|G|$ and dispose of the base case] We induct on $n := |G|$. If $n \leq 5$, assign each vertex of $G$ a distinct colour in $\{1, 2, 3, 4, 5\}$; this is a proper colouring using at most $5$ colours, so $\chi(G) \leq 5$. Fix $n \geq 6$ and assume $\chi(H) \leq 5$ for every planar graph $H$ with $|H| < n$. Let $G$ be a planar graph with $|G| = n$, fixed together with a planar embedding. [/step] [step:Pick a vertex $x$ of degree at most $5$] By the corollary to Euler's formula for planar graphs, every planar graph has a vertex of degree at most $5$: the inequality $e(G) \leq 3|G| - 6$ (valid for simple planar graphs with $|G| \geq 3$) gives average degree at most $6 - 12/|G| < 6$, so some vertex has degree at most $5$. Pick $x \in V(G)$ with $\deg x \leq 5$. Apply the inductive hypothesis to the planar graph $G - x$ (which has $n - 1 < n$ vertices and inherits a planar embedding): there exists a proper $5$-colouring $c: V(G - x) \to \{1, 2, 3, 4, 5\}$. [/step] [step:Reduce to the case $\deg x = 5$ with all five colours on $N(x)$] If $\deg x \leq 4$, or more generally if the multiset $\{c(y) : y \in N(x)\}$ misses some colour $\alpha \in \{1, 2, 3, 4, 5\}$, extend $c$ to $G$ by setting $c(x) := \alpha$. The extension is proper: for every edge $xy \in E(G)$, $c(x) = \alpha \neq c(y)$. This gives $\chi(G) \leq 5$ and completes the inductive step. The remaining case is $\deg x = 5$ and the five neighbours of $x$ receive five distinct colours. Label the neighbours in the cyclic order induced by the planar embedding (reading counter-clockwise around $x$) as $x_1, x_2, x_3, x_4, x_5$, and relabel the colours so that $c(x_i) = i$ for $i = 1, 2, 3, 4, 5$. [/step] [step:Define Kempe chains and attempt the $\{1,3\}$-swap] For a pair of distinct colours $\{\alpha, \beta\} \subset \{1, 2, 3, 4, 5\}$, the *$\{\alpha, \beta\}$-Kempe subgraph* is the subgraph of $G - x$ induced on the vertex set $c^{-1}(\alpha) \cup c^{-1}(\beta)$. Its connected components are called *$\{\alpha, \beta\}$-Kempe chains*. *Key swap property.* Let $C$ be a connected component of the $\{\alpha, \beta\}$-Kempe subgraph. Define $c': V(G - x) \to \{1, 2, 3, 4, 5\}$ by \begin{align*} c'(v) := \begin{cases} \beta & \text{if } v \in C \text{ and } c(v) = \alpha, \\ \alpha & \text{if } v \in C \text{ and } c(v) = \beta, \\ c(v) & \text{otherwise.} \end{cases} \end{align*} Then $c'$ is a proper $5$-colouring of $G - x$. To verify, consider any edge $uv \in E(G - x)$. If both $u, v \in C$, they receive opposite colours under $c$ (as an edge inside the Kempe subgraph between an $\alpha$-vertex and a $\beta$-vertex), hence swapped they still differ. If both $u, v \notin C$, $c'(u) = c(u) \neq c(v) = c'(v)$. If exactly one endpoint — say $u$ — is in $C$ and the other $v$ is not, then $v \notin C$ means either $c(v) \notin \{\alpha, \beta\}$, in which case $c'(u) \in \{\alpha, \beta\}$ and $c'(v) = c(v) \notin \{\alpha, \beta\}$ so they differ; or $c(v) \in \{\alpha, \beta\}$ but $v$ lies in a different Kempe component from $u$, in which case $uv$ would connect the two components — a contradiction with $C$ being a maximal connected component. So $uv$ does not exist in this sub-case. Now attempt the $\{1, 3\}$-swap. Let $C_1$ be the connected component of the $\{1, 3\}$-Kempe subgraph that contains $x_1$. *Sub-case A: $x_3 \notin C_1$.* Apply the swap property to $C_1$ with $(\alpha, \beta) = (1, 3)$ to obtain a proper $5$-colouring $c'$ of $G - x$ with $c'(x_1) = 3$ and $c'(x_3) = c(x_3) = 3$. Crucially $x_2, x_4, x_5$ are unchanged: they receive colours $2, 4, 5$ respectively (they cannot lie in $C_1$, since $C_1 \subseteq c^{-1}(1) \cup c^{-1}(3)$ and $c(x_2) = 2 \notin \{1, 3\}$; similarly for $x_4, x_5$). So the five neighbours of $x$ receive colours $\{3, 2, 3, 4, 5\}$ under $c'$, missing colour $1$. Extend $c'$ to $G$ by setting $c'(x) := 1$; this is a proper $5$-colouring of $G$, giving $\chi(G) \leq 5$. *Sub-case B: $x_3 \in C_1$.* Then there is a path in $G - x$ from $x_1$ to $x_3$ using only vertices of colours $1$ and $3$. Call this path $\pi_{13}$. [guided] The Kempe-chain idea is a two-colour recolouring. We look at the subgraph induced by the vertices of colours $1$ and $3$, call it the $\{1,3\}$-Kempe subgraph, and study its connected components. If we swap colours $1 \leftrightarrow 3$ on *one full connected component*, the result is still a proper colouring: within the component the edges are preserved (they flip from $1$-$3$ to $3$-$1$), outside the component no vertex is affected, and on the boundary of the component there are no edges to worry about because if there were such an edge $uv$ with $u$ in the component and $v$ outside, then either $c(v) \notin \{1, 3\}$ (no conflict with the swap) or $c(v) \in \{1, 3\}$ but $v$ is in a different component — but then $uv$ connects two different components of the $\{1,3\}$-Kempe subgraph, which is impossible by the definition of a connected component. The swap operates on a **single** connected component — this is the critical point. If we swap on *all* of $c^{-1}(1) \cup c^{-1}(3)$ (i.e., all components at once), we just permute the names of the two colours globally and nothing useful happens. Swapping on just one component breaks the symmetry between $x_1$ and $x_3$. We now apply this to $x_1$ and $x_3$. Let $C_1$ be the connected component of the $\{1, 3\}$-Kempe subgraph containing $x_1$. There are two cases: - If $x_3 \notin C_1$, the swap on $C_1$ recolours $x_1$ from $1$ to $3$ while leaving $x_3$ with colour $3$. After the swap, the neighbours of $x$ receive colours $(3, 2, 3, 4, 5)$. Colour $1$ is now missing at all five neighbours, so we can assign colour $1$ to $x$ and extend the colouring. Done. - If $x_3 \in C_1$, there is a $\{1,3\}$-coloured path $\pi_{13}$ from $x_1$ to $x_3$ inside $G - x$. The swap no longer helps: it would flip both $x_1$ and $x_3$ to colour $3$ and $1$ respectively, still using both colours. We must turn to the symmetric pair. [/guided] [/step] [step:Attempt the $\{2,4\}$-swap in parallel] Repeat the analysis with $\{2, 4\}$ in place of $\{1, 3\}$. Let $C_2$ be the connected component of the $\{2, 4\}$-Kempe subgraph containing $x_2$. *Sub-case A': $x_4 \notin C_2$.* Swapping colours $2$ and $4$ on $C_2$ gives a proper $5$-colouring $c'$ of $G - x$ in which $c'(x_2) = 4$, $c'(x_4) = 4$, and $c'(x_1), c'(x_3), c'(x_5) \in \{1, 3, 5\}$ are unchanged. Colour $2$ is missing at all five neighbours, so setting $c'(x) := 2$ extends to a proper $5$-colouring of $G$. *Sub-case B': $x_4 \in C_2$.* Then there is a path in $G - x$ from $x_2$ to $x_4$ using only colours $2$ and $4$. Call it $\pi_{24}$. [/step] [step:Derive a planar-embedding contradiction when both Kempe chains exist] Suppose we are in sub-cases B and B' simultaneously: both paths $\pi_{13}$ and $\pi_{24}$ exist in $G - x$. Consider the closed curve $\gamma_{13}$ in the plane formed by concatenating the planar embedding of $\pi_{13}$ with the two straight edges $x\,x_1$ and $x\,x_3$ (these edges come from the planar embedding of $G$). This curve is a Jordan curve in the plane (it is a simple closed curve, being the boundary of a cycle in the planar embedding). By the Jordan curve theorem, $\gamma_{13}$ separates the plane into two open regions: an interior $\mathrm{Int}(\gamma_{13})$ and an exterior $\mathrm{Ext}(\gamma_{13})$. In the cyclic order $x_1, x_2, x_3, x_4, x_5$ around $x$, the vertex $x_2$ sits between $x_1$ and $x_3$ on one side, while $x_4$ sits between $x_3$ and $x_1$ on the other side (going through $x_5$). Therefore, in any planar embedding of the five edges $x\,x_i$, the vertex $x_2$ lies strictly on one side of $\gamma_{13}$ and $x_4$ lies strictly on the other — one is in $\mathrm{Int}(\gamma_{13})$, the other in $\mathrm{Ext}(\gamma_{13})$. The path $\pi_{24}$ goes from $x_2$ to $x_4$ inside the planar embedding of $G - x$. Since $x_2$ and $x_4$ lie on opposite sides of $\gamma_{13}$, the path $\pi_{24}$ must intersect $\gamma_{13}$ in at least one point. The intersection cannot lie on either of the two edges $x\,x_1$ or $x\,x_3$ (these have only $x$ and $x_1$ or $x_3$ as their endpoints, and $\pi_{24}$ avoids $x$ entirely, lying in $G - x$; it could pass through $x_1$ or $x_3$ only by sharing a vertex with $\pi_{13}$). So the intersection occurs at a vertex $z$ that lies on both $\pi_{13}$ and $\pi_{24}$. But $z \in \pi_{13}$ forces $c(z) \in \{1, 3\}$, and $z \in \pi_{24}$ forces $c(z) \in \{2, 4\}$. Since $\{1, 3\} \cap \{2, 4\} = \varnothing$, no such vertex $z$ can exist. This is a contradiction. [guided] We are in the case where both Kempe swaps fail — there is a $\{1,3\}$-path $\pi_{13}$ from $x_1$ to $x_3$ in $G - x$ and a $\{2,4\}$-path $\pi_{24}$ from $x_2$ to $x_4$ in $G - x$. We argue this configuration is geometrically impossible in a planar embedding. Form the closed curve $\gamma_{13}$ by concatenating the planar image of $\pi_{13}$ (from $x_1$ to $x_3$ in $G - x$) with the two drawn edges $x\,x_3$ and $x\,x_1$ (going back through the centre $x$). Because $G$ is planarly embedded and $\pi_{13}$ is a simple path in $G - x$, this gives a simple closed curve in the plane — a **Jordan curve**. By the **Jordan curve theorem**, $\gamma_{13}$ bounds two open regions of the plane: an interior $\mathrm{Int}(\gamma_{13})$ and an exterior $\mathrm{Ext}(\gamma_{13})$. Every continuous path in the plane that crosses from interior to exterior must meet $\gamma_{13}$. Now examine where $x_2$ and $x_4$ lie. Around the vertex $x$ in the planar embedding, the five edges $x\,x_1, x\,x_2, x\,x_3, x\,x_4, x\,x_5$ appear in cyclic order. The Jordan curve $\gamma_{13}$ passes through $x$ along the edges $x\,x_1$ and $x\,x_3$, so locally near $x$ it divides the small neighbourhood of $x$ into two sectors. One sector contains the edges going to $x_2$ (which lies cyclically between $x_1$ and $x_3$), while the other contains the edges going to $x_4$ and $x_5$ (which lie cyclically between $x_3$ and $x_1$ on the "other side"). Hence $x_2$ and $x_4$ lie on opposite sides of $\gamma_{13}$ — one in the interior, the other in the exterior. The path $\pi_{24}$ is a continuous curve from $x_2$ to $x_4$ drawn in the plane as part of the planar embedding of $G$. Since its endpoints are on opposite sides of $\gamma_{13}$, $\pi_{24}$ must cross $\gamma_{13}$ at some point. Where does the crossing occur? In the planar embedding, two edges of $G$ can only "cross" by sharing a vertex (planar embedding means no edge crossings). So the crossing happens at a vertex — call it $z$ — that lies simultaneously on $\pi_{13}$ (which is part of $\gamma_{13}$, excluding the point $x$ and the two straight edges which the path $\pi_{24}$ in $G - x$ cannot run through except at $x_1$ or $x_3$) or at one of the two drawn edges $x\,x_1$, $x\,x_3$. A careful case analysis: the path $\pi_{24}$ lies inside $G - x$, so it avoids $x$; hence it cannot cross the edges $x\,x_1$ or $x\,x_3$ anywhere except at $x_1$ or $x_3$. But $c(x_1) = 1 \notin \{2, 4\}$ and $c(x_3) = 3 \notin \{2, 4\}$, while every internal vertex of $\pi_{24}$ has colour in $\{2, 4\}$, so $\pi_{24}$ cannot pass through $x_1$ or $x_3$. Therefore the crossing occurs strictly inside the path portion of $\gamma_{13}$, i.e., at a vertex $z \in \pi_{13}$. Now we have $z \in \pi_{13}$ and $z \in \pi_{24}$. The first forces $c(z) \in \{1, 3\}$ (every vertex on $\pi_{13}$ has such a colour); the second forces $c(z) \in \{2, 4\}$. These two requirements are incompatible since $\{1, 3\} \cap \{2, 4\} = \varnothing$. Contradiction. [/guided] [/step] [step:Conclude] The contradiction in the previous step rules out sub-case B combined with sub-case B'. Therefore at least one of sub-cases A, A' holds, and we have exhibited a proper $5$-colouring of $G$. By induction, $\chi(G) \leq 5$ for every planar graph $G$. This completes the proof. [illustration:kempe-jordan-obstruction] [/step]