Start Doing Graph Theory © 2025 by Mikhail Lavrov is licensed under CC BY-SA 4.0
This part of the book is all about planar graphs: graphs that can be drawn in the plane (or on a flat sheet of paper) with no crossing edges.
Chapter 21 will introduce the fundamental notions of planar graphs, as well as the tools we will use to analyze them. Building on this, Chapter 22 discusses several ways to determine whether or not a graph is planar without having to go through lots of painful trial and error.
Chapter 23 lifts these ideas up to three dimensions to answer questions about polyhedra. These problems have been studied since Plato’s day, long before the invention of graph theory, but we can use graph theory to solve them.
Chapter 24 is about the map coloring problem. It includes a brief historical overview of the journey from the start of graph theory to the four color theorem. We will also prove some easier results, and end by looking at an extension of the problem.
Start Doing Graph Theory © 2025 by Mikhail Lavrov is licensed under CC BY-SA 4.0