Short proofs of theorems of Nash-Williams and Tutte (Q2713657)

In this nice paper short proofs for the theorems mentioned in the title are given. Also, it is proved that each theorem can be easily derived from the other. Let \(G=(V,E)\) be an undirected graph that may have multiple edges but no loops. The Nash-Williams theorem says that a graph \(G\) can be edge-partitioned into \(k\) acyclic subgraphs iff \(|E(X)|\leq k(|X|-1)\) for every nonempty \(X\subset V\). Tutte's theorem says that a graph \(G\) can be edge-partitioned into \(k\) connected spanning subgraphs iff \(|E(P)|\geq k(|P|-1)\) for every partition \(P\) of \(V\). Here \(E(X)\) are edges spanned by \(X\), \(E(P)\) are edges joining different parts of \(P\), and \(|P|\) is the number of parts in \(P\).