Dual graphs, planar graphs, and the graph theory reformulation
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.
Choose a map and watch the dual graph appear step by step. First, a vertex is placed at the center of each region. Then, edges are drawn between vertices whose regions share a border. 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.
Place vertices and connect them with edges to build your own graph. The system checks for edge crossings in real time -- crossing edges turn red. Try dragging vertices to eliminate crossings. Can you always rearrange a graph to avoid crossings? Try building K5 (the complete graph on 5 vertices) to see a graph that cannot be drawn without crossings no matter how you arrange the vertices.
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.
See the equivalence in action. Click a region on the map or a vertex in the dual graph to cycle through four colors. Both views update simultaneously. When two adjacent regions (or connected vertices) share the same color, the conflict is highlighted in red in both views 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.