Hello, I have enrolled in my college's "Design and Analysis of Algorithms" course. Recently we were studying Greedy algorithms and proving their correctness. I have a doubt about the correctness proof of Prim's Algorithm. How do we prove that it does not form a cycle during its execution? In the following snippet from our lecture slides, it says:
"No cycles ever get created in T. Why? Consider any iteration with current sets X and T. Suppose e gets added. Key point: e is the first edge crossing (X, V-X) that gets added to T -> its addition can't create a cycle in T (by Lonely Cut Corollary). QED!" For clarification, T is the set of edges that Prim's algorithm has included to be a part of MST at a point in time during its execution. X is the set of vertices that are already included in the MST. V is the set of all vertices of the input graph. V-X is the set of vertices which are not yet been included int the output Spanning tree.
Definition of Empty Cut Lemma: https://ibb.co/9wnHPtF Definition of Double crossing Lemma and Lonely Cut Corollary: https://ibb.co/fGqm9Xh Algorithm/Pseudocode stated in lecture slides: https://ibb.co/SnP9Vc6
How are we using the Lonely cut corollary in the part highlighted with yellow in the above image to prove that cycles won't form in the output spanning tree?
I have searched many resources on the internet for my doubts (including CodeForces blogs), but I am not able to find a reasonable explanation for the above question. Please help.
Thank you.
