Question

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

Answer 1

Edge disjoint spanning trees are spanning trees that do not have any edges in common.

Kn has n(n-1)/2 edges ,and each spanning has n-1 edges so there are at most Floor[n/2] edges disjoint spanning tree.

Comments

Why floor[n/2] and not ceil[n/2]..can you please explain in detail

---

Consider K3 graph it has 1 edge disjoint spanning tree if u will take ceil then u will get 2 edge disjoint spanning tree which is not possible.

---

but in k5

3 edges are disjoint spanning

---

no for K5 you have 2 disjoint edge spanning tree...

---