From the Five-Color Theorem to Explicit Colorings
A proof that every finite simple plane graph can be colored with at most five colors gives a guarantee, but an explicit coloring requires keeping track of the embedding as well as the edges. The key step is to delete a vertex, color what remains, and then reinsert the vertex. If all five colors occur among its neighbors, a Kempe-chain swap can make one color available.
Throughout, a plane graph is a graph together with a fixed drawing in the plane in which edges meet only at common endpoints. All graphs in this tutorial are finite and simple: they have no loops or multiple edges. A proper coloring assigns colors to vertices so that the endpoints of every edge receive different colors. We use the palette \(\{1,2,3,4,5\}\). The cyclic embedding order around a vertex is the clockwise order of its neighbors in the fixed drawing.
The low-degree vertex lemma for finite simple plane graphs and the five-color theorem were established in the earlier material on planar graphs and map coloring. In particular, the finite simple hypothesis matters: loops prevent proper coloring, and parallel edges can give degree greater than five without adding distinct neighbors. The examples below use only finite simple plane graphs.
Kempe Components and Safe Swaps
Proof. Let \(C\) be a component of the subgraph induced by colors \(i,j\). Every edge within \(C\) joins differently colored vertices, since the original coloring is proper. Interchanging \(i\) and \(j\) at both endpoints of such an edge leaves their colors different. Now consider an edge with one endpoint \(x\in C\) and the other endpoint \(y\notin C\). If \(y\) had color \(i\) or \(j\), then \(y\) would be in the induced subgraph and adjacent to \(x\), so it would belong to the same component \(C\), a contradiction. Thus \(y\) has neither color \(i\) nor color \(j\), and the swap cannot create a conflict on \(xy\). Edges with neither endpoint in \(C\) are unchanged. Hence the coloring remains proper. \(\square\)
The crucial case for reinsertion is when a deleted vertex \(v\) has five neighbors, one in each color. Name them \(a,b,c,d,e\) in clockwise order, with colors \(1,2,3,4,5\), respectively. If \(a\) and \(c\) lie in different components of the 1-3 subgraph, swap the component containing \(a\). This changes \(a\)'s color from 1 to 3, while \(c\) remains color 3, so no neighbor of \(v\) has color 1. If they are in the same component, planar separation makes a different swap possible.
Proof. If \(v\) has degree at most four, at most four colors occur on its neighbors, so at least one of the five colors is absent there and can be assigned to \(v\). The same argument applies if \(v\) has five neighbors but their colors are not all distinct: at most four colors then occur among them.
It remains to consider five neighbors \(a,b,c,d,e\) in clockwise order with distinct colors \(1,2,3,4,5\), respectively. If \(a\) and \(c\) are in different components of the 1-3 subgraph of \(G-v\), swap the component containing \(a\). No neighbor of \(v\) then has color 1, so assign color 1 to \(v\).
Otherwise, choose a simple path from \(a\) to \(c\) in the 1-3 subgraph of \(G-v\). Together with the edges \(av\) and \(cv\), this path forms a simple closed curve in the plane. The cyclic order around \(v\) places \(b\) and \(d\) on opposite sides of that curve. A path from \(b\) to \(d\) in the 2-4 subgraph would have to cross the curve. It cannot meet the curve at a vertex, since the curve's vertices have colors 1 and 3, not 2 or 4; and edges in a plane graph cannot cross except at common endpoints. Therefore \(b\) and \(d\) are in different components of the 2-4 subgraph. Swap the component containing \(b\). This changes \(b\) from color 2 to color 4 while \(d\) remains color 4, so color 2 is now absent from the neighbors of \(v\). Assign color 2 to \(v\). In each case the coloring extends properly to \(G\). \(\square\)
Worked Colorings
Worked Example: A Four-Neighbour Reinsertion
Let \(G\) have vertex set \(V=\{v,a,b,c,d\}\) and edge set \(E=\{va,vb,vc,vd,ab,bc,cd,da\}\). Embed \(a,b,c,d\) in that clockwise order on a square, and put \(v\) inside the square, joined to all four corners. Delete \(v\); its embedding order is \(a,b,c,d\).
The remaining graph is the square with edges \(ab,bc,cd,da\). Assign colors \(a=1,b=2,c=1,d=2\). Check the four edges: \(ab\) has colors \(1,2\); \(bc\) has \(2,1\); \(cd\) has \(1,2\); and \(da\) has \(2,1\). Thus the coloring of \(G-v\) is proper. The neighbors of \(v\) use only colors 1 and 2, so color 3 is available. Assign \(v=3\).
Check: The four edges incident to \(v\) have color pairs \((3,1),(3,2),(3,1),(3,2)\), so none is monochromatic. Together with the four checked square edges, this verifies the coloring on all eight edges.
Worked Example: Swapping a Disconnected Kempe Component
Let \(G\) have vertex set \(V=\{v,a,b,c,d,e\}\) and edge set \(E=\{va,vb,vc,vd,ve\}\). Draw the five edges as spokes from \(v\), with clockwise order \(a,b,c,d,e\) around \(v\). Delete \(v\); this is the embedding order at the deleted vertex.
Color the five isolated vertices of \(G-v\) by \(a=1,b=2,c=3,d=4,e=5\). This is proper because \(G-v\) has no edges. The 1-3 subgraph has vertices \(a,c\) and no edges, so its components are the singletons \(\{a\}\) and \(\{c\}\). Swap colors 1 and 3 on \(\{a\}\). Now \(a=3\), while \(c=3\); the swap is valid because \(a\) and \(c\) are not adjacent.
After the swap the neighbors of \(v\) have colors \(3,2,3,4,5\), so color 1 is absent. Assign \(v=1\). The five edges \(va,vb,vc,vd,ve\) now have endpoint color pairs \((1,3),(1,2),(1,3),(1,4),(1,5)\), all different at their endpoints. This checks every edge of \(G\).
Worked Example: A Connected 1-3 Chain and a 2-4 Swap
Let \(G\) have vertex set \(V=\{v,a,b,c,d,e\}\) and edge set \(E=\{va,vb,vc,vd,ve,ab,bc,cd,de,ea,ac\}\). Draw \(a,b,c,d,e\) as a pentagon in clockwise order and \(v\) inside it, joined to all five vertices. Draw the extra edge \(ac\) outside the pentagon. This gives a plane embedding: the added edge lies outside the pentagon and does not cross the spokes. Delete \(v\); the clockwise order around it is \(a,b,c,d,e\).
Color the remaining vertices \(a=1,b=2,c=3,d=4,e=5\). All five cycle edges \(ab,bc,cd,de,ea\) have differently colored endpoints, and the extra edge \(ac\) has endpoint colors 1 and 3. Hence this is a proper coloring of \(G-v\).
The 1-3 subgraph has vertices \(a,c\) and edge \(ac\), so \(a\) and \(c\) are connected. The 2-4 subgraph has vertices \(b,d\) and no edge, so its components are \(\{b\}\) and \(\{d\}\). Swap colors 2 and 4 on \(\{b\}\) only. The resulting colors are \(a=1,b=4,c=3,d=4,e=5\). The edge \(bc\) now has colors \(4,3\), and \(ab\) has colors \(1,4\); the other cycle edges remain properly colored, as does \(ac\), with colors \(1,3\).
Now color \(v=2\), which is absent from its neighborhood. The five spoke edges have endpoint color pairs \((2,1),(2,4),(2,3),(2,4),(2,5)\), so each is proper. The cycle and chord were checked above, verifying all eleven edges.
Check: The two-color components used were computed in the relevant induced subgraphs: \(G-v\) restricted to colors 1 and 3 contains exactly \(a,c,ac\), while its restriction to colors 2 and 4 contains exactly the isolated vertices \(b,d\). The swap changes only \(b\), not \(d\).
Why the Embedding Order and the Exact Swap Matter
The cyclic order is not decorative information. In the last example, the 1-3 path \(a,c\), together with \(av\) and \(cv\), separates \(b\) from \(d\). That separation is what ensures that the 2-4 component containing \(b\) does not contain \(d\). Without the plane embedding, the argument that a safe swap exists would be missing.
A useful record for each deletion step is: the deleted vertex, its neighbors in clockwise order, the colors of those neighbors, and the components of the two relevant two-color subgraphs. Then state which component is swapped and which color is assigned on reinsertion. If the graph has several components, the same procedure applies within each component; there are no edges between components to create coloring conflicts.
Common mistake: swapping both components. In the last example, a tempting but incorrect calculation is to swap colors 2 and 4 on all vertices of those colors. That changes both \(b=2\) and \(d=4\), leaving \(d=2\). Color 2 is then still used on a neighbor of \(v\), so assigning \(v=2\) would make edge \(vd\) monochromatic. The correction is to swap only the component containing \(b\): since \(b\) and \(d\) are disconnected in the 2-4 subgraph, \(d\) remains color 4 and color 2 becomes available for \(v\).
These examples show three distinct situations: a color is already available; a two-color component can be swapped because the relevant vertices are disconnected; and a connected chain of the first color pair forces use of the other pair. In every case, the final check is against the full edge list, not just the edges incident to the reinserted vertex.
Check Your Understanding
For each question, identify the relevant colors and verify any proposed coloring against the specified edges.
- In the square-with-center example, why is color 3 available when \(v\) is reinserted?
- For a proper coloring, explain why a vertex outside a Kempe component cannot have either of that component's two colors and be adjacent to it.
- In the pentagon example, list the vertices and edges of the 1-3 subgraph of \(G-v\).
- In that same example, what would go wrong if the 2-4 swap changed both \(b\) and \(d\)?
- Why does the proposition require a plane embedding in the case where the 1-3 component connects \(a\) to \(c\)?