Correctness of Prim's algorithm and Kruskal's algorithm

The basic idea of the proof, the cut property, is presented in the first 2 minutes of the video. I encourage you to try and prove the correctness of Prim’s algorithm and Kruskal’s algorithm on your own once you know what the cut property is.

If you can’t prove it yourself, watch the full video to understand why Prim’s algorithm works. Thereafter, you can prove Kruskal’s algorithm as an exercise.