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](https://drive.google.com/file/d/19Hzd8-Bwe--uxnMaLzNkpL9TfuNpkXqs/view?usp=sharing) (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:↵
↵
1. 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.↵
↵
2. V is the set of all vertices of the input graph.↵
↵
3. X is the set of vertices that are already included in the output tree. ↵
↵
4. 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↵
↵
<a href="https://ibb.co/hVTkrRx"><img src="https://i.ibb.co/9WdJB9m/slide.png" alt="slide" border="0"></a>↵
↵
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.↵
↵
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](https://drive.google.com/file/d/19Hzd8-Bwe--uxnMaLzNkpL9TfuNpkXqs/view?usp=sharing) (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:↵
↵
1. 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.↵
↵
2. V is the set of all vertices of the input graph.↵
↵
3. X is the set of vertices that are already included in the output tree. ↵
↵
4. 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↵
↵
<a href="https://ibb.co/hVTkrRx"><img src="https://i.ibb.co/9WdJB9m/slide.png" alt="slide" border="0"></a>↵
↵
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.↵
↵
