Abstract:

The famous Nash-Williams' Theorem states that the edge set of a multigraph $G=(V,E)$ can be decomposed into $k$ forests iff for every subset $X\subseteq V$ the induced subgraph $G[X]$ contains at most $k(|X|-1)$ edges. In 2017, Glebov conjectured that if a graph $G$ satisfies the conditions of Nash-Williams' Theorem and has minimum degree $\delta(G)\ge k+1$, then its edge set can be decomposed into $k$ forests such that none of these forests has an isolated vertex. Here we prove this conjecture. Moreover, we present a new proof of Nash-Williams' Theorem which allows us to prove a more general result on edge decomposition of a  multigraph into $k$ forests such that the size of connected components in these forests is greater than a given constant.