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.

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email