Re:Graph Coloring, or Proof by Crayon
by jscipione on Tuesday December 18, 2012 @03:18PM
(#4939365)
I don't understand why the Costa Rica example is 3-colorable. The green province in the middle touches 5 other provinces so it seems like it should be 5-colorable.
[ Parent
| on HN ]
Re:Graph Coloring, or Proof by Crayon
by ColinWright on Tuesday December 18, 2012 @03:48PM
(#4939501)
Consider a pizza sliced into six pieces. Each piece touches only their neighbor on each side, so you can color them alternately red and blue. Now suppose someone carved an island in the middle around an olive that no one wants. That touches all six, but can still be colored green, so we use only three colors in total, despite the middle "region" having six neighbors.