2
$\begingroup$

Consider an undirected, simple graph $G= (V,E)$ with edge weights $w_e\geq 0$,$e \in E$. Then any two minimum spanning trees$T_1$ and $T_2$ for $G$ must have a nonempty intersection, that is $T_1 \cap T_2 \neq \varnothing$

I know that even if the edge weights are not all identical you can have two disjoint minimum spanning trees. But how do I prove this mathematically?

$\endgroup$
  • 2
    $\begingroup$ But if you can have two disjoint MSTs then the problem statement is false. Is it a prove or disprove question? In which case just state your counterexample. $\endgroup$ – bitesizebo Apr 7 '18 at 15:36
  • $\begingroup$ Perhaps the question is meant to be "Under what conditions must two minimum spanning trees for $G$ have a nonempty intersection"? $\endgroup$ – Math1000 Apr 7 '18 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.