Nash-Williams theorem
Theorem in graph theory describing number of edge-disjoint spanning trees a graph can have / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Nash-Williams theorem?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
In graph theory, the Nash-Williams theorem is a tree-packing theorem that describes how many edge-disjoint spanning trees (and more generally forests) a graph can have:
A graph G has t edge-disjoint spanning trees iff for every partition where there are at least t(k − 1) crossing edges (Tutte 1961, Nash-Williams 1961).[1][2]
For this article, we will say that such a graph has arboricity t or is t-arboric. (The actual definition of arboricity is slightly different and applies to forests rather than trees.)