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 K_{5} with four colors? Does the result contradict the four-color theorem?

PROBLEM SET 23.2:

PROBLEM SET 23.4:

PROBLEM SET 23.5:

PROBLEM SET 23.6:

PROBLEM SET 23.7:

PROBLEM SET 23.8: