Five Color Theorem

Status
Zombie
Title
Test
Date
Excerpt
Published
Sep 9, 2021
Tags
Feature on homepage
Theorem. A planar graph can be colored with at most five colors.
Proof sketch. A planar graph must have a vertex, say , of degree at most five (why?). Testing...
Let be a 5-coloring of the graph (by the 🎩 induction hypothesis).

If has:
  • [Case 1] less than five neighbors in , or
  • [Case 2] five neighbors that have a repeated color amongst them
then: (πŸ€” click toggle to find out what happens.)
can be easily extended to a coloring of by using the β€œmissing color” on the vertex .
Β 

Β 
Otherwise, has five neighbors, all colored with distinct colors. Assume, WLOG, that the vertices in the neighborhood of , denoted appear clockwise in a fixed planar drawing of the graph . Suppose we have:
red, blue, green, purple, orange
Β 

Β 
Consider the subgraphs and consisting of only the red and green; and the blue and purple vertices of , respectively (with respect to the coloring ).
We now have the following.
  • If and do not belong to the same connected component of , then swap the colors red and green in the connected component containing to go to Case 2.
  • If and do not belong to the same connected component of , then swap the colors red and green in the connected component containing to go to Case 2.
  • If neither of the above hold, then:
    • there is a red-green path from to and
    • there is a blue-purple path from and .
    • We now have a contradiction, because... (πŸ€” click the toggle to reveal the spoiler!)
      ...these paths MUST cross, but -
      • they cannot cross at an edge (planarity) and
      • they cannot cross at a vertex (because of the coloring).
      This is a contradiction.
Β 

Β 
Ta-da! πŸŽ‰
Β 
Β 
Β