Use planar topology in coloring and dual graphs

Try

Planar graphs have vertices of degree at most five, suggesting an induction for coloring. If a removed vertex has at most four differently colored neighbors, one of five colors is free. The difficult case has five neighbors using all five colors. A color exchange along a connected two-color component can free a color, and planarity guarantees that two obstructing exchanges cannot both be blocked.

Predict

Predict why recoloring just one neighbor may fail. Its other neighbors could already use the new color. Instead swap two colors on an entire connected component of the subgraph induced by those colors. Every internal edge remains properly colored, and no boundary edge joins to an outside vertex of either swapped color, because that would put it in the same component. This is a Kempe-chain exchange.

Experiment

Label the five neighbors around the removed vertex in cyclic order.

Neighbor	Initial color	First exchange candidate
v1	1	Colors 1 and 3
v2	2	Colors 2 and 4
v3	3	Colors 1 and 3
v4	4	Colors 2 and 4
v5	5	Unchanged

Try the first exchange only on the component containing v1. If it does not contain v3, color one becomes free at the removed vertex. Explain why swapping both components would fail to free that color.

Understand

The five-color theorem follows by induction on vertex count. The planar edge bound gives average degree below six for n≥3, hence a vertex v of degree at most five. Color G−v inductively. Only the case of five distinct neighbor colors needs repair. If v1 and v3 lie in different components of the colors-one-and-three subgraph, swap the component containing v1 and give v color one. Otherwise a simple alternating path joins v1 to v3. Together with edges v₁v and vv₃ it forms a simple closed curve. The cyclic order places v2 and v4 on opposite sides. A path using only colors two and four between them would have to cross this curve, but it cannot meet its colors-one-and-three path or pass through the removed v. Thus v2 and v4 are in different two-four components. Swap the component containing v2 and give v color two. This completes the induction.

Apply

A related planar construction is the dual graph: place one vertex in each face of a connected plane graph and one dual edge across each original edge, joining its two incident faces. Loops and parallel edges can arise even when the original graph is simple. A bridge has the same face on both sides and becomes a dual loop. A cycle in the primal separates faces and corresponds to a cut structure in the dual; a precise cycle–bond correspondence needs the chosen embedding and minimality conditions. The dual is therefore attached to a plane embedding, not merely to an abstract graph without further qualifications.

Continue

The four-color theorem is stronger, but its proof is not supplied by this five-color exchange. A naive attempt to repeat the same argument with four neighbors can fail because earlier swaps alter later connectivity. Do not promote the five-color proof into a four-color claim. For a practical coloring certificate, check every edge after any exchange. The lesson’s geometric step relies on plane separation of a simple closed curve; it is explicitly the topological ingredient that has no analogue in an arbitrary crossing-rich graph.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with maximize edges under clique restrictions.