Nash-Williams theorem

Statement

In graph theory, the Nash-Williams theorem is a tree-packing theorem that describes how many edge-disjoint spanning trees (and more generally forests) a graph can have:

A graph G has t edge-disjoint spanning trees iff for every partition $V_1, \ldots, V_k \subset V(G)$ where $V_i \neq \emptyset$ there are at least t(k − 1) crossing edges.

The theorem was proved independently by Tutte and Nash-Williams, both in 1961. In 2012, Kaiser gave a short elementary proof.