Given a plane graph we can form a new graph by drawing a vertex in the middle of each of 's faces, and joining vertices if their corresponding faces are adjacent.
iff connected and .
Always as each edge in the original graph may be crossed at most once by an edge in the dual. If is then has a bridge, which certainly will not be crossed by an edge in the dual, so . If is then there is an edge, which if removed, would leave a bridge in . so again . In both cases .
If then any pair of faces has at most a single common boundary edge so .
A plane map is a plane graph together with its set of faces.
A (face) colouring of a plane map is an assignment of colours to the faces of the map with the condition that faces sharing an edge have different colours.
Let be a plane graph with every vertex of even degree. Then every face in the dual has an even number of sides.
Therefore every cycle in the dual is even, so the dual is bipartite, so there is a face colouring of with just two colours.
The four colour conjecture (4CC) asserts that every plane map can be 4-face coloured. Alternatively every plane graph has by considering the dual.
The 4CC was made popular by Cayley in 1878. Almost at once, ``proofs'' appeared: Kempe 1879, Tait 1880.
John Fremlin 2010-02-17