2025/10/16 by Erika Bérczi-Kovács, András Frank, Bérczi-Kovács, Erika +1 · 1 voice
#cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.2510.23614
One of the major starting points of discrete optimization is the theorem of Nash-Williams and Tutte on the existence of k disjoint spanning trees of a graph, along with its counterpart on the existence of k forests covering all edges of the graph. These elegant results triggered comprehensive research that gave rise to far-reaching generalizations and found applications in seemingly distant areas. Our first goal is to elucidate some aspects of these developments with the hope that the story finds its way to non-experts. But we hope that experts will also find some novelty in our exposition.