Nash-Williams theorem

A k-arboric graph is necessarily k-edge connected. The converse is not true.

As a corollary of NW, every 2k-edge connected graph is k-arboric.

Both NW and Menger's theorem characterize when a graph has k edge-disjoint paths between two vertices.

NW (1964) generalized the above result to forests:

G can be partitioned into t edge-disjoint forests iff for every ${\displaystyle U\subset V(G)}$, the induced subgraph G[U] has size ${\displaystyle |G[U]|\leq t(|U|-1)}$.

A proof is given here.[2][1]

This is how people usually define what it means for a graph to be t-aboric.

In other words, for every subgraph S = G[U], we have ${\displaystyle t\geq \lceil E(S)/(V(S)-1)\rceil }$. It is tight in that there is a subgraph S that saturates the inequality (or else we can choose a smaller t). This leads to the following formula

${\displaystyle t=\lceil \max _{S\subset G}{\frac {E(S)}{V(S)-1}}\rceil }$

also referred to as the NW formula.

The general problem is to ask when a graph can be covered by edge-disjoint subgraphs.

• Arboricity
• Bridge (cut edge)
• Menger's theorem
• Tree packing conjecture

• Paulson, Lawrence C. The Nash-Williams partition theorem (Formal proof development in Isabelle/HOL, Archive of Formal Proofs)