The Four-Color Theorem and Basic Graph Theory

Description

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? Contents Introduction Chapter 1 Exercises 2 The Four-Color Theorem Chapter 2 Exercises 3 Triangulation Chapter 3 Exercises 4 Euler’s Formula Chapter 4 Exercises 5 Complete Graphs and Bigraphs Chapter 5 Exercises 6 Maximal Planar Graphs Chapter 6 Exercises 7 Kempe Chains Chapter 7 Exercises 8 A Few Notable Planar Graphs Chapter 8 Exercises 9 Counting Ways Chapter 9 Exercises 10 Logic Puzzle Chapter 10 Exercises 11 Trivial Four-Coloring Chapter 11 Exercises 12 Separating Triangles Chapter 12 Exercises 13 Hamiltonian Cycles Chapter 13 Exercises 14 Polygon Graphs Chapter 14 Exercises 15 Adding Edges Chapter 15 Exercises 16 Ultimate Four-Coloring Chapter 16 Exercises 17 Removing Edges Chapter 17 Exercises 18 Vertex Splitting Chapter 18 Exercises 19 Quadrilateral Switching Chapter 19 Exercises 20 Kirchhoff’s Rules Chapter 20 Exercises 21 Building Blocks Chapter 21 Exercises 22 Four-Coloring by Pairing Faces Chapter 22 Exercises 23 The Three-Edges Theorem Chapter 23 Exercises 24 A Recoloring Technique Chapter 24 Exercises 25 Kempe’s Problem Revisited Chapter 25 Exercises 26 Degrees of Separation Chapter 26 Exercises 27 A Handwaving “Proof” of the 4CT Chapter 27 Exercises 28 Random Notes 28.1 No Vertices with Degree Two 28.2 Degree Three Vertices Don’t Connect 28.3 Degree Number Degeneracy 28.4 Maximum Degrees 28.5 Attempts at Disproof 28.6 The Currently Accepted Proof of the 4CT 28.7 Other Surfaces 28.8 3D Space 28.9 Three-Color Theorems 28.10 Two-Coloring 28.11 A Couple of Cool Graphs… Just Because Chapter 28 Exercises Answers to Chapter 1 Maps vs. Graphs Answers to Chapter 2 The Four-Color Theorem Answers to Chapter 3 Triangulation Answers to Chapter 4 Euler’s Formula Answers to Chapter 5 Complete Graphs and Bigraphs Answers to Chapter 6 Maximal Planar Graphs Answers to Chapter 7 Kempe Chains Answers to Chapter 8 A Few Notable Planar Graphs Answers to Chapter 9 Counting Ways Answers to Chapter 10 Logic Puzzle Answers to Chapter 11 Trivial Four-Coloring Answers to Chapter 12 Separating Triangles Answers to Chapter 13 Hamiltonian Cycles Answers to Chapter 14 Polygon Graphs Answers to Chapter 15 Adding Edges Answers to Chapter 16 Ultimate Four-Coloring Answers to Chapter 17 Removing Edges Answers to Chapter 18 Vertex Splitting Answers to Chapter 19 Quadrilateral Switching Answers to Chapter 20 Kirchhoff’s Rules Answers to Chapter 21 Building Blocks Answers to Chapter 22 Four-Coloring by Pairing Faces Answers to Chapter 23 The Three-Edges Theorem Answers to Chapter 24 A Recoloring Technique Answers to Chapter 25 Kempe’s Problem Revisited Answers to Chapter 26 Degrees of Separation Answers to Chapter 27 A Handwaving “Proof” of the 4CT Answers to Chapter 28 Random Notes Was This Book Helpful? About the Author