This refers to some of the slides and perhaps the notes.
The presented security proof for Kruskal's algorithm is pretty complex in terms of notation and argumentation. It has notation for the first k edges chosen by the algorithm, and the first k of an arbitrary MST (sorted by weight), and shows that the latter can be "transformed" into the former without increasing the weight.
There is a simpler approach that proceeds via the "safe greedy choice" property. This shows that for every (committed) choice the algorithm makes (edge added to the set), it is possible for the current set to be extended to a full MST. In other words, no choice commits the algorithm to an ultimately suboptimal result. Since the algorithm eventually outputs a spanning tree, this output must be optimal.
This refers to some of the slides and perhaps the notes.
The presented security proof for Kruskal's algorithm is pretty complex in terms of notation and argumentation. It has notation for the first k edges chosen by the algorithm, and the first k of an arbitrary MST (sorted by weight), and shows that the latter can be "transformed" into the former without increasing the weight.
There is a simpler approach that proceeds via the "safe greedy choice" property. This shows that for every (committed) choice the algorithm makes (edge added to the set), it is possible for the current set to be extended to a full MST. In other words, no choice commits the algorithm to an ultimately suboptimal result. Since the algorithm eventually outputs a spanning tree, this output must be optimal.