Find a graph, as simple as possible, that cannot be vertex colored with three colors. Why is this of interest in connection with Prob. 24? Data from Prob. 24 The famous four-color theorem states that one can color the vertices of any planar graph (so that adjacent vertices get different colors) with at most four colors. It had been conjectured

Chapter 23, PROBLEM SET 23.8 #25

Find a graph, as simple as possible, that cannot be vertex colored with three colors. Why is this of interest in connection with Prob. 24?

Data from Prob. 24

The famous four-color theorem states that one can color the vertices of any planar graph (so that adjacent vertices get different colors) with at most four colors. It had been conjectured for a long time and was eventually proved in 1976 by Appel and Haken. Can you color the complete graph K5 with four colors? Does the result contradict the four-color theorem?

Related Book For answer-question

Advanced Engineering Mathematics

10th edition

Authors: Erwin Kreyszig

ISBN: 978-0470458365