Lesson 3

Theorem. Any planar graph is 6-colorable.

Proof. We proceed by induction. As we already know, a planar graph has a vertex \(v\) of degree at most five. Remove it from the graph. The graph remains planar. Thus, by induction, it can be colored, after which we return the vertex \(v\), for which there will certainly remain an unused color.◼