Prove that for $k \geq 4$, a graph with $k$ vertices can have exactly 2 edge-disjoint minimum spanning trees

109 Views Asked by At

Prove that for $k \geq 4$, a graph with $k$ vertices can have exactly 2 edge-disjoint minimum spanning trees.

I can define a graph as I wish, but it must hold that for $k\geq 4$, there are two min-cost spanning trees, and both of them are edge disjoint. There can be many more spanning trees, but neither of them is the min-cost, and neither of them are edge-disjoint with respect to one another. I am also allowed to define the edge weights.

I was thinking that I could define my graph with every vertex connected to every other vertex, and the paths of the minimum spanning trees have weight $1$, while the path of everything else has $\infty$.

But then the question becomes, how do I describe how I figure out 'two disjoint edge-spanning trees'?