Nash-Williams Proof Golf

Let $G$ be a loopless undirected multigraph and a $\rho$-forest decomposition of $G$ be a partition $E(G) = \coprod_{i = 1}^\rho E_i$ such that each subgraph $\langle E_i \rangle$ edge-induced by edge part $E_i$ is a forest. Call $\langle E_i \rangle$ a subforest of $G$ for each $i = {,}_{j = 1}^\rho j$. The smallest $\rho$ such that $G$ admits a $\rho$-forest decomposition is the edge arboricity $\rho(G)$ of $G$.

Theorem

If $\lvert V(G) \rvert > 1$ then

for the subgraph relation $<$.

Proof

Consider any $H < G$. Let $n_H = \lvert V(H) \rvert$, $m_H = \lvert E(H) \rvert$. Then $\rho(H)(n_H - 1) \geq m_H$. That is, the number of disjoint subforests of $H$ times the maximum number ($n_H - 1$, when the subtree spans $H$) of edges per subforest of $H$ is at least the number of edges in $H$.

(I.e., total num subforests * max edges per subforest ≥ total edges.)

Therefore $\rho(H) \geq \frac{m_H}{n_H - 1}$.

To prove the other direction, let $G$ be a counterexample that minimizes $n_G + m_G$; i.e., $\rho(G) > \max_{H < G} \lceil \frac{\lvert E(H) \rvert}{\lvert V(H) \rvert - 1} \rceil$. $G$ must be connected, or else one of its components $G^\prime < G$ would be a smaller counterexample. Also, $\rho(G - e) < \rho(G)$ for each edge $e \in E(G)$, because if there were some $e \in E(G)$ such that $\rho(G - e) \geq \rho(G)$, then $G - e$ would be a smaller counterexample. Call this property arboreal criticality.

Lemma

For connected arboreally critical $G$ with order at least 2 and any $e \in E(G)$, all $(\rho(G) - 1)$-forest decompositions of $G - e$ consist of $\rho(G) - 1$ disjoint spanning trees of $G$. That is, the decomposition of $G - e$ is maximal in some sense corresponding to how the decomposition of $G$ was minimal in the sense of arboreal criticality — removing any edge decreases $G$’s arboricity.

To prove the lemma, consider a counterexample decomposition ${,}_{i = 1}^{\rho(G) - 1} E_i$ of $G - e$ so that some part, say $E_1$, doesn’t edge-induce a spanning tree. $G$ was critical, so adding $e%$ back to $G - e$ increases the minimum number of subforests we need, so in particular $\langle E_1 + e \rangle$ has a cycle containing $e$. This means $e$’s endpoints are in the same component $Q < \langle E_1 \rangle < G$ of $\langle E_1 \rangle$. We assumed $\langle E_1 \rangle$ doesn’t span $G$, and $Q$ is a component of $\langle E_1 \rangle$, so $V(Q) \neq V(G)$.

Now consider $Q^\ast = G[Q]$, the subgraph vertex-induced by $Q$ in $G$. $E(G) \setminus E(Q^\ast)$ is nonempty — otherwise $G$ and $Q^\ast$ would have the same edges and $G$ wouldn’t be connected. Further, $G$ is arboreally critical, so $Q^\ast$ has a $(\rho(G) - 1)$-forest decomposition $E(Q^\ast) = \coprod_{i = 1}^{\rho - 1} Q^{\ast\prime}_i$.

Note that in $({,}_{i = 1}^{\rho(G) - 1} E_i, { e })$, the component $Q$ of $\langle E_1 \rangle$ spans $Q^\ast$ and $e \in Q^\ast$, because $Q^\ast$ was defined that way. Consider the set $S$ of $\rho(G)$-forest decompositions of $G$ that have a component of the first part, $E^\prime_1$, that spans $Q^\ast$ and contains edge $e^\prime$. Let $\overline{E} = ({,}_{i = 1}^{\rho(G) - 1} \overline{E}_i, { \overline{e} })$ be a $\rho$-forest decomposition in $S$ that maximizes $\mathscr{I}(\overline{E}) = \sum_{i = 1}^{\rho(G) - 1} \lvert A_i \cap \overline{E}_i \rvert$. Note that $\overline{e} \in Q^\ast$ and so $\overline{e} \in Q^{\ast\prime}_t$ for some $t$. As before, $\langle \overline{E}_t + \overline{e} \rangle$ has a cycle $C$ in $Q^\ast$ containing $\overline{e}$. If $t = 1$, then $C \subseteq Q^\ast$, because $\overline{E} \in S$ and any element of $S$ has a $Q^\ast$-spanning component of its first part and a singleton part whose element is in $E(Q^\ast)$. Otherwise, if $t \neq 1$ and $C \nsubseteq Q^\ast$, then there is some edge $\overline{e}^\prime \in E(C)$ with an endpoint in $V(Q^\ast)$ and other endpoint in $V(G) \setminus V(Q^\ast)$. Adding $\overline{e}^\prime$ to $\langle \overline{E}_1 \rangle$ would create a new edge-induced subgraph $\langle \overline{E}_1 + \overline{e}^\prime \rangle$, which would be acyclic, because $\langle \overline{E}_1 \rangle$ is a forest, $Q^\ast$ is edge-induced (in $G$) by $\overline{E}_1$, and $\overline{e}^\prime$’s endpoint in $V(G) \setminus V(Q^\ast)$ is adjacent to exactly one vertex in $V(Q^\ast)$. Further, $\langle \overline{E}_t + \overline{e} - \overline{e}^\prime \rangle$ would be acyclic, because $\overline{e}^\prime \in E(C)$ creates the unique cycle $C$ from $\langle \overline{E}_t \rangle$ in $Q$, and removing $\overline{e}^\prime$ from $C$ breaks it. But then we get a $(\rho(G) - 1)$-forest decomposition $\overline{E}^\prime = ({,}_{i = 1}^{t - 1} \overline{E}_i, \overline{E}_t + \overline{e} - f, {,}_{i = t + 1}^{\rho(G) - 1} \overline{E}_i)$ of $G$, contradicting the definition of $\rho(G)$. On the other hand, if $t \neq 1$ and $C \subseteq Q^\ast$, then we can select some edge $\overline{e}^{\prime\prime} \in E(C) - A_t \subset E(Q)$ to construct $\overline{E}^{\prime\prime} = ({,}_{i = 1}^{t - 1} \overline{E}, \overline{E}_t + \overline{e} - \overline{e}^{\prime\prime}, {,}_{i = t + 1}^{\rho(G) - 1} \overline{E}_i, { \overline{e}^{\prime\prime} })$. This partition is perfectly valid, similarly to before, but now $\overline{e}^\prime \in A_t$ has been moved into $\overline{E}_t + \overline{e}$ (and $\overline{e}^{\prime\prime} \notin A_t$ has been moved out of $\overline{E}_t$), so that $\mathscr{I}(\overline{E}^{\prime\prime}) > \mathscr{I}(\overline{E})$. Absurdum.

I like trees, so I like forests. Sometimes they’re hard to see though. This is partly an exercise in showing my notes, in a case where the notes result from explicitating some source material, then distilling back down, mostly on the fly. This incurred a pretty big blowup for the intermediate stuff. It surprised me how much effort it took me to unpack then repack the paper — “A Short Proof of Nash-Williams’[s] Theorem for the Arboricity of a Graph” — which totals one and a half pages, almost all proof golf.