NASH‐WILLIAMS’ THEOREM ON DECOMPOSING GRAPHS INTO FORESTS

2013/08/06 by Christian Reiher, Lisa Sauermann
Computer Science · Mathematics · #Advanced Graph Theory Research #Fundamental theorem #Generalization #Geometric and Algebraic Topology #Limits and Structures in Graph Theory #Simple (philosophy) #Statement (logic) #Structured program theorem #math.CO

paper · pdf · doi:10.1112/s0025579313000119

published as Mathematika 60 (2014) 32-36 · This version differs slightly from the version published by the Journal

openalex publication_date 2013/08/06 · openalex created_date 2016/06/24 · arxiv created 2017/05/03 · arxiv updated 2017/05/05 · openalex updated_date 2026/08/05

Abstract

We give a simple graph-theoretic proof of a classical result due to Nash-Williams on covering graphs by forests. Moreover, we derive a slight generalization of this statement where some edges are preassigned to distinct forests.

Citations

• Decomposition of Finite Graphs Into Forests
• A short proof of Nash-Williams' theorem for the arboricity of a graph
• Edge-Disjoint Spanning Trees of Finite Graphs
• On the Problem of Decomposing a Graph into n Connected Factors