Four color theorem
Task number: 4190
Prove the four-color theorem for planar graphs without triangles.
Hint
First, show the existence of a vertex of bounded degree.
Solution
A planar graph without triangles contains a vertex of degree at most three: if all vertices had degree at least 4, the estimate \( | E_G | \ le2 | V_G | -4 \) would not hold.
We proceed by induction, we remove such a vertex, and color the rest by the induction hypothesis. The coloring can be extended to the removed vertex, because neighbors block at most three colors from four.
