I want to show that the output spanning tree $S$ of Kruskal's algorithm is a minimum spanning tree, so it is of minimum weight, by contradiction.
We suppose that $S$ is not a minimum spanning tree.
Let $T$ be a spanning tree which has the minimum weight.
How can I go on to get a contradicti...
@user159870 prove the following claim (called cycle property): "an edge can be on the mst if and only if it is not the heaviest edge on any cycle" and then show that kruskal algorithm may give you no edges that are heaviest on any cycle.
@Juho arXiv now has our preprint on generalising the idea for stick cutting to proportional apportionment here. (Beware, not as polished as our stick cutting paper. What can I say, there was I deadline.)
@Raphael Nice! I skimmed through it; nice that you have some practical considerations there as well. Is there something wrong with the caption of Fig 1?
The two questions marks make me wonder if there is a missing label reference or something
@Juho Um, yea, the references to the plot failed for some reason. I'm sure I had no such warning locally. Let me check... damns you, ages-old TeX Live on arXiv!
@Juho Jup, to ESA. (Thankfully, local compilation shows the references to the submitted PDF has them. Which plot is for which algorithm is kind of relevant there...)
I want to show that the output spanning tree $S$ of Kruskal's algorithm is a minimum spanning tree, so it is of minimum weight, by contradiction.
We suppose that $S$ is not a minimum spanning tree.
Let $T$ be a spanning tree which has the minimum weight.
How can I go on to get a contradicti...
