Nash-Williams theorem
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 formula_1 where formula_2 there are at least "t"("k" − 1) crossing edges (Tutte 1961, Nash-Williams 1961).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.)
Q131476
graph theory
Concept
None
tree-packing
UNK
Q831672
spanning tree
Concept
Q272735
forests
Concept
Q1391861
Tutte
PER
Q3002796
Nash-Williams
PER
Q4784907
arboricity
Concept
Q65066994
Nash-Williams theorem
UNK
1961-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1961
DATE
1961-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1961
DATE
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
studies
studies
field of work
field of work