A short proof of Nash-Williams' theorem for the arboricity of a graph (Q1323488)

The authors give a self-contained short proof of Nash-Williams' formula \[ \rho(G)= \max_{H< G} \lceil q(H)/(p(H)- 1)\rceil \] for the edge- arboricity \(\rho(G)\) of a graph (with possible multiple edges but no loops). Here \(H\) runs over all subgraphs of \(G\) with \(p(H)= \# V(H)> 1\) and \(q(H)= \# E(H)\). The proof easily follows from the following lemma which is proved in detail. Lemma: Let \(G\) be a connected arboricity critical graph with \(p(G)> 1\). Then for any \(e\in E(G)\), any \((\rho(G)-1)\)-forest decomposition of \(G-e\) is a decomposition into \(\rho(G)-1\) spanning trees of \(G\).