The Hadwiger Conjecture

A special place in the theory of vertex-colorings of a graph is occupied by the so-called four-color problem the question whether there is a four-coloring of a planar map such that every pair of coimtries that share a (nonpoint) boundary segment receive different colors. Let us show the weaker five-color theorem. Before we can prove it, we need a standard fact, which is a special case of the Euler-Poincare formula. 

Theorem 17.3. Let G he a nonempty finite connected graph, drawn in a plane without self intersections. Let R G) denote the set of regions into which the plane is divided. Then we have the following formula  

Assume now that we have at least one edge. If G has no cycles (in particular no loops), then G is a tree. It is then well known that in this case, E(G) = (G) - -1. Since also i (G) = 1, we get (17.1). 

Lemma 17.4. An arbitrary planar simple graph G has a vertex with valency at most 5. 

Every loopless planar graph is five-colorable. 

---