1
$\begingroup$

This question already has an answer here:

My gut says it's true and I have tested it on a few examples. However, I can't prove it. I thought of using contradiction; suppose there exists another tree T' with smaller weight which has m edges not shared with the first tree. We can transform the first tree to second one in m steps by adding one of the m edges which are only in T' and removing one edge off the tree which belongs only to the first tree in each step. The weight of the tree should decrease in at least one of these steps. Take the added edge in that step add it to the first tree and remove an edge and prove that it decreases the weight which contradicts with the weight of the tree cannot be decreased.


I couldn't work out the quirks. Is the statement even true? Why?

$\endgroup$

marked as duplicate by David Richerby, Evil, Discrete lizard, Yuval Filmus, Tom van der Zanden Aug 31 '18 at 11:11

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.