How to prove every $2^k$-edge-connected graph has $k$ edge disjoint spanning trees?

Question

Tutte] Every $2^k$-edge-connected graph has $k$ edge-disjoint spanning trees. Proof: Apply the matroid intersection theorem.

Anyone see how this proof is suppose to work?

Answer 1

Call your graph $G=(V,E).$ Let $M_1$ be the direct sum of $k$ copies of the graphic matroid of $G,$ and let $M_2$ be the partition matroid where a set of edges $F\subseteq [k]\times E$ is independent iff each $e\in E$ is used at most once. The matroid intersection theorem says that $E$ can be split into $k$ disjoint connected spanning graphs if and only if

$$\min_{F_1,\dots,F_k\subseteq E}\left(r(F_1)+\dots+r(F_k)+\left|\bigcup_{i=1}^k (E\setminus F_i)\right|\right)= k(n-1)$$ where $r$ denotes the rank of the graphic matroid.

If an edge in some $F_i$ isn't in $\bigcap_{i=1}^n F_i,$ it might as well be removed - this won't increase the value inside the min. So the minimum is achieved when all the $F_i$ are equal. And then any edge between two vertices that are already connected in $F_1$ might as well be added to all the $F_i,$ again because this won't increase the value inside the min. With these reductions the only thing that matters is the connected components of $F_1.$ (Where if a vertex isn't used by any edge in $F_1,$ it counts as a separate component.)

Let $\mathcal P$ denote a partition of $V,$ let $\ell(\mathcal P)$ denote the number of components of the partition $\mathcal P,$ and let $|E\setminus \mathcal P|$ denote the number of edges that go between different parts of $\mathcal P.$ The condition reduces to

$$\min_{\mathcal P}(k(n-\ell(\mathcal P))+|E\setminus \mathcal P|)= k(n-1).$$

If your graph is $2k$-edge-connected then for any non-trivial partition each part must have at least $2k$ edges connecting it to other parts, giving at least $k\cdot \ell(\mathcal P)$ edges total. So the value inside the min is at least $kn$ for non-trivial partitions, and the minimum $k(n-1)$ is achieved by the trivial partition. To get the title result note that $2^k\geq 2k$ for $k\geq 1.$