Dual graphs, planar graphs, and the graph theory reformulation
Put a dot in every region, join neighbors with a line, and a puzzle about maps turns into a puzzle about graphs.
Choose a map and press Build Dual Graph. Watch a vertex land in each region, then an edge appear wherever two regions share a border.
The key insight that unlocked the four color problem was a change of perspective: instead of coloring regions on a map, we can color vertices in a graph. Given any map, place a vertex at the center of each region. Whenever two regions share a border (not just a point), connect their vertices with an edge. The resulting graph is called the dual graph of the map.
This dual graph is always planar -- it can be drawn in the plane without any edge crossings, because we constructed it from a map on the plane. Coloring the map so that no two neighboring regions share a color is now exactly the same as coloring the vertices of the dual graph so that no two adjacent vertices share a color. This reformulation transforms a geographic puzzle into a combinatorial one, opening the door to the full machinery of graph theory.
Notice how the graph captures all the adjacency information of the map.
Key insight: Every map has a dual graph, and coloring the map is exactly the same as coloring the dual graph. The dual of a map drawn on the plane is always a planar graph.
This reformulation opened the door -- attacking the problem with graph theory tools like Euler's formula, Kempe chains, and reducibility became possible once the problem was stated in the language of graphs
Click the canvas to add vertices, click two vertices to join them, and drag vertices to untangle the red crossings. Then build K5 -- five vertices all joined to each other -- and notice one crossing always remains.
Click canvas to add vertices. Click one vertex then another to connect them. Drag vertices to reposition. Crossing edges turn red.
Key insight: A planar graph is one that can be drawn in the plane without edge crossings. Not all graphs are planar -- K5 (the complete graph on 5 vertices) and K3,3 (the complete bipartite graph on 3+3 vertices) cannot be drawn without crossings.
Click a region or a vertex to cycle its color. Both views change together, and a clash turns red in both at once.
Key insight: Map coloring and graph coloring are two views of the same problem. The four color theorem equivalently states that every planar graph is 4-colorable.
Spot a mistake or have an idea?