Talk:Arboricity
From Wikipedia, the free encyclopedia
[edit] Recent redefinition by Phaunt
Phaunt (talk · contribs) changed the lede sentence to read "The arboricity of an undirected graph is the size of the minimum forest into which its edges can be partitioned." I believe it is wrong in multiple ways, so I reverted, but it may be worth more discussion here.
- First, if a graph has cycles, its edges cannot be partitioned into a single forest. A forest is a single graph with no cycles, or equivalently the disjoint union of trees. If one partitions the edges of a cyclic graph into disjoint trees, the trees are not disjoint, so it is not a forest.
- Second, the "size" of a forest is unclear and it is not obvious that it refers to the number of trees.
- Third, the number of trees into which the edges of a graph can be partitioned is not the same as arboricity. Consider, e.g., a dumbell graph formed by two cycles connected by a single bridge edge. Its arboricity is two (it is easy to partition the edges into two forests: just make one forest consist of an edge from each cycle, and the other forest consist of all the rest of the edges) but if one tries to partition its edges into trees, three trees are required.
—David Eppstein 03:15, 15 August 2007 (UTC)
