Euler’s Formula – Let G be a connected plane graph with n vertices, m edges, and l faces.  Then n-m+l = 2.

ex. n = 8 vertices, m = 14 edges, l = 8 faces

n-m+l = 8-14+8 = 2 ڤ

Corollary – A plane graph with n ≥ 3 vertices has at most 3n-6 edges.

* From this we get: d(G) = 2m/n ≤ 2(3n - 6)/n < 6 *

4-color theorem – Every planar graph is 4-colorable.

5-color theorem – Every planar graph is 5-colorable. 

6-color theorem – Every planar graph is 6-colorable.


The 6-color theorem proof

Proof by induction. 

Trivial with planar graph with at most 6 vertices.  We can easily produce a 6 coloring with one color for each vertex.

Now, suppose that G is simple planar with n vertices, and that all simple planar graphs with n-1 vertices are 6 colorable. 

G must contain a vertex v of degree at most 5. 

If we delete v and it’s incident edges, the remaining graph has (n-1) edges and is thus 6-colorable. 

A 6-coloring of G is obtained by coloring v with a different color from the (at most 5) vertices adjacent to v.  ڤ

6-Coloring Greedy Algorithm

1. Sort the vertices according to Smallest Vertex Ordering.

2. For i = 1,...n.


Complexity Analysis

We can sort the vertices (step 1) in O(nlogn) time and the loop takes O(n) time giving us an overall complexity of O(n).


PREVIOUS: Definitions    NEXT: 5-Color Theorem