Part V: Hard Problems

These four chapters have a thematic connection: for the first time in this book, the problems we discuss are too hard to solve in a large graph, even with the aid of a computer.

Chapter 17 is about Hamilton cycles: cycles that pass through every vertex of a graph. The Hamilton cycle problem is one I am personally very fond of, and it might also be said to be one of the oldest problems in graph theory. We will start from knight’s tours of chessboards and end with degree conditions sufficient to guarantee the existence of a Hamilton cycle.

Chapter 18 is about two opposite notions: cliques (sets of vertices that are all adjacent) and independent sets (sets of vertices with no edges between them). These are interesting objects in their own right, but we will also see the proof of Ramsey’s theorem, which tells us a bit about the relationship between them.

Chapter 19 introduces the graph coloring problem. (It was historically first used for coloring maps, but you will have to wait until Chapter 24 for that application.) We will see lower and upper bounds, algorithms that sometimes achieve them. We will look at examples in which the bounds are very very good, and examples in which they are horrid.

In Chapter 20, we will make all the hard problems easy. We will do this by looking at line graphs. Solving a “vertex” problem in a line graph is equivalent to solving an “edge” problem in a different graph, which will reveal connections between the hard problems introduced in the previous three chapters, and easier problems that we looked at earlier in this book.