The Four-Color Theorem and Basic Graph Theory

Explore a variety of fascinating concepts relating to the four-color theorem with an accessible introduction to related concepts from basic graph theory. From a clear explanation of Heawood’s disproof of Kempe’s argument to novel features like quadrilateral switching, this book by Chris McMullen, Ph.D., is packed with content. It even includes a novel handwaving argument explaining why the four-color theorem is true. * What is the four-color theorem? * Why is it common to work with graphs instead of maps? * What are Kempe chains? * What is the problem with Alfred Kempe’s attempted proof? * How does Euler’s formula relate the numbers of faces, edges, and vertices? * What are Kuratowski’s theorem and Wagner’s theorem? * What is the motivation behind triangulation? * What is quadrilateral switching? * What is vertex splitting? * What is the three-edges theorem? * Is there an algorithm for four-coloring a map or graph? * What is a Hamiltonian cycle? * What is a separating triangle? * How is the four-color theorem like an ill-conditioned logic puzzle? * Why is the four-color theorem true? * What makes the four-color theorem so difficult to prove by hand?