Answer to Question #118957 in Discrete Mathematics for inv

Question

1. Construct a proof for the five color theorem for every planar graph.

Answer 1

Theorem: Every planar graph with n vertices can be colored using at most 5 colors.

Proof by induction, we induct on n, the number of vertices in a planar graph G.

Base case, P(n≤5): Since there exist ≤5 nodes in G, the graph can be colored using 5 colors.

Inductive step, P(n+1): Assuming P(n)

P(n) is true, that is, every planar graph with n vertices, we need to show P(n)

P(n) is true.

We know every planar graph has one vertex with deg(v)≤5. We call this vertex v in our graph G. Remove v and for the remaining subgraph G′ we can assume P(n).

If deg⁡(v)≤4, we can color all vertices adjacent to v using 4 colors and use color 5 to color v itself to reach a valid coloring.

If deg⁡(v)=5, we assume that all vertices adjacent to v are colored in different colors.

Hence proved.