Search code examples
edgesupperboundspanning-tree

Edge disjoint spanning trees

I have come across a question based on spanning tree i.e :

what is the upper bound on the number of edge disjoint spanning trees in a
complete graph of n vertices?

(a) n      (b) n-1
(c) [n/2]  (d) [n/3]

what do we mean by edge disjoint spanning trees? Does that mean different trees such that they don't have any same edges in all the trees?as disjoint means nothing common. Please explain and also what should be its answer then?

Solution

  • Yes. Edge disjoint spanning trees are spanning trees that do not have any edges in common. The maximum number of edge disjoint spanning trees is also known as 'spanning tree packing number or STP number'. For more details regarding this, you can look at this article http://www.sciencedirect.com/science/article/pii/S0012365X00000662#.