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 (from Page No. 58, the MST part starts), 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 any point in time during its execution.
V is the set of all vertices of the input graph.
X is the set of vertices that are already included in the output tree.
V-X is the set of vertices which are not yet been included int the output tree.
Definition of a Cut of a graph: https://postimg.cc/SJsMFKJ7
Definition of Empty Cut Lemma: https://postimg.cc/JsQdQ8bV
Definition of Double crossing Lemma and Lonely Cut Corollary: https://postimg.cc/5QFR5Fmn
Algorithm/Pseudocode stated in lecture slides: https://postimg.cc/nsBrWdhJ
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.
