**
5-Color Theorem**

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

*Proof:*

Proof by contradiction.

Let G be the smallest planar graph (in terms of number of vertices) that cannot be colored with five colors.

Let v be a vertex in G that has the maximum degree. We know that deg(v) < 6 (from the corollary to Euler’s formula).

__ Case #1__: deg(v) ≤
4. G-v can be colored with five colors.

There are at most 4 colors that have been used on the neighbors of v. There is at least one color then available for v.

So G can be colored with five colors, a contradiction.

__ Case #2__: deg(v) =
5. G-v can be colored with 5 colors.

If two of the neighbors of v are colored with the same color, then there is a color available for v.

So we may assume that all the vertices that are adjacent to v are colored with colors 1,2,3,4,5 in the clockwise order.

Consider all the vertices being colored with colors 1 and 3 (and all the edges among them).

If this subgraph G is
disconnected and v_{1} and v_{3} are in different components,
then we can switch the colors 1 and 3 in the component with v_{1}.

This will still be a 5-coloring
of G-v. Furthermore, v_{1} is colored with color 3 in this new
5-coloring and v_{3} is still colored with color 3. Color 1 would be
available for v, a contradiction.

Therefore v_{1} and v_{3}
must be in the same component in that subgraph, i.e. there is a path from v_{1}
to v_{3} such that every vertex on this path is colored with either
color 1 or color 3.

Now, consider all the vertices being
colored with colors 2 and 4 (and all the edges among them). If v_{2}
and v_{4 }don't lie of the same connected component then we can interchange the colors in the chain starting at v_{2
}and use left over color for v.

If they do lie on the same
connected component then there is a path from
v_{2} to v_{4} such that every vertex on that path has either
color 2 or color 4.

This means that there must be two edges that cross each other. This contradicts the planarity of the graph and hence concludes the proof. ڤ

PREVIOUS: Theorems NEXT: Algorithm