Start Doing Graph Theory © 2025 by Mikhail Lavrov is licensed under CC BY-SA 4.0
In this part of the book, I cover topics related to the connectivity of graphs: how resilient they are to being disconnected by removing vertices or edges. This is the last part of the book (other than the appendix), and so I will spend a bit more time drawing connections to topics from previous chapters.
Chapter 25 starts with the most simple case: understanding cut vertices, whose removal disconnects a graph all by itself. Graphs with no cut vertices are said to be 2-connected, and we will study 2-connected graphs by looking at their ear decompositions: a good example of a graph-theoretical structure which is friendly to induction.
Chapter 26 generalizes this notion to sets of vertices and sets of edges whose removal can disconnect a graph. Our exploration of this topic culminates in Menger’s theorem, but we will not prove it until Chapter 27, because its proof is rather long. (After proving it, we will also see some of its theoretical applications.)
The last chapter of the book, Chapter 28, takes an algorithmic approach. Here, we look at solving the maximum flow problem. This gives us another angle on Menger’s theorem, and in particular gives us an algorithm to determine the connectivity of a graph.
Start Doing Graph Theory © 2025 by Mikhail Lavrov is licensed under CC BY-SA 4.0