chapter 10Graph Theory

An early-morning walk is a blessing for the whole day.

—Henry David Thoreau (1817–1862)

In Section 1.4 we introduced some elementary facts about graphs that were useful in subsequent chapters. In this chapter, we’ll expand the discussion and introduce some important areas of graph theory. In the first three sections, we’ll introduce the basic types of graphs along with some results about the structure of graphs. The rest of the chapter is devoted to introducing the matching problem, two famous traversal problems, the planarity problem, and the coloring problem.

10.1 Definitions and Examples

For the most part, we will refer to the basic notions and notations for graphs presented in Section 1.4. We’ll start by introducing ...

Get Discrete Structures, Logic, and Computability, 4th Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.