Start Doing Graph Theory © 2025 by Mikhail Lavrov is licensed under CC BY-SA 4.0
This part of the book is about trees: graphs which are minimally connected. This concept is at the root of every branch of graph theory, and I’m sure that reading the fruit of my labors will leaf you amazed at how useful trees can be.
Chapter 9 introduces trees through one specific application: spanning trees. A spanning tree is a skeleton that connects a graph with no redundancy or wasted edges. This notion has practical applications, but it is important theoretically as well. With the idea of spanning trees as our goal, we will discover what the definition of a tree should be, motivating the chapters to come.
Chapter 10 goes into more detail about the properties of trees. Once we have these results in our toolbox, trees actually become useful for solving problems about graphs, and we will see several examples of this.
Chapter 11 explores a beautiful solution to a very specific problem: given a fixed set of vertices, and our choice of which edges to include, how many different trees can we make? There are many possible proofs; I have chosen to tell you this story through Prüfer codes.
Finally, Chapter 12 goes in a somewhat different direction: it is about directed acyclic graphs, and how studying these can help us understand the ways that a directed graph can be connected.
Start Doing Graph Theory © 2025 by Mikhail Lavrov is licensed under CC BY-SA 4.0