Lesson 14

We will also use the following theorem of Nash-Williams: if a graph is \(2r\)-edge-connected, then it contains \(r\) edge-disjoint spanning trees. The theorem itself is a substantial result, so here we use it as a tool.

First we need one small parity claim. If \(T\) is a spanning tree of a graph \(G=(V,E)\), then there exists a set \(A\subseteq T\) such that \((E\setminus T)\cup A\) is even. To find \(A\), start with \(U=E\setminus T\). Repeatedly take a leaf \(v\) of the current tree. If the degree of \(v\) in \(U\) is odd, add to \(U\) the unique tree edge incident to \(v\); otherwise add nothing. Then delete \(v\) from the current tree. When a vertex is deleted, its degree in \(U\) has been made even and will never change again. At the end, the last remaining vertex is also even because the sum of all degrees in \(U\) is even.