Plane graphs

Definition 9..1 (Dual graph $G*$)  

Given a plane graph $G$ we can form a new graph $G*$ by drawing a vertex in the middle of each of $G$'s faces, and joining vertices if their corresponding faces are adjacent.

Lemma 9..2 (Condition for duality of dual)  

$G** = G$ iff $G$ connected and $\lambda(G) > 2$.

Proof. If $G*$ is always connected, so $G**$ is as well, so $G$ must be.

Always $e(G*) \le e(G)$ as each edge in the original graph may be crossed at most once by an edge in the dual. If $\lambda(G)$ is $1$ then $G$ has a bridge, which certainly will not be crossed by an edge in the dual, so $e(G*) < e(G)$. If $\lambda(G)$ is $2$ then there is an edge, which if removed, would leave a bridge in $G$. so again $e(G*) < e(G)$. In both cases $e(G**) \le e(G*) < e(G)$.

If $\lambda(G) \ge 3$ then any pair of faces has at most a single common boundary edge so $G** = G$.

$\qedsymbol$

Definition 9..3 (Plane map)  

A plane map is a plane graph together with its set of faces.

Definition 9..4 (Face colouring)  

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.

Example 9..5  

Let $G$ 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 $G$ with just two colours.

Definition 9..6 (Four colour conjecture)  

The four colour conjecture (4CC) asserts that every plane map can be 4-face coloured. Alternatively every plane graph has $\chi(G) \le 4$ by considering the dual.

The 4CC was made popular by Cayley in 1878. Almost at once, ``proofs'' appeared: Kempe 1879, Tait 1880.