Garrett Ervin


Carnegie Mellon University


Monday, June 7, 2021 - 4:00pm to 5:30pm



There are many duality theorems in both finite and infinite graph theory that relate the maximum number of disjoint paths through a given graph G to the minimum size of a cut-set disconnecting G. The quintessential example is Menger's theorem, which says that the maximum number of vertex disjoint paths between two vertices x and y in a finite graph G is equal to the minimum size of a vertex cut disconnecting x and y.

We present a general approach to proving path/cut-set duality theorems for locally finite graphs. As one consequence of this approach, we give novel proofs of Menger's theorem and another classical duality result due to Halin. As another, we prove the following general existence theorem, which can be viewed as a maximal extension of König's lemma: given an infinite, locally finite connected graph G and a vertex x in G, there is a pruned tree T contained in G and rooted at x that, in a precise sense, splits as early and as often as possible.