### RahulHarpal's blog

By RahulHarpal, history, 2 months ago,

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:

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

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.

• -3

 » 2 months ago, # |   0 Auto comment: topic has been updated by RahulHarpal (previous revision, new revision, compare).
 » 2 months ago, # |   0 Auto comment: topic has been updated by RahulHarpal (previous revision, new revision, compare).
 » 2 months ago, # |   +12 Instead of $V - X$ I will write $V\setminus X$ as I'm more used to this notation.Lemma 1: If a set of edges $T$ doesn't have cycles, and an edge $e$ is not in any cycle in $T\cup \{e\}$, then $T\cup \{e\}$ doesn't have any cycles. Proof:Proof by contradiction:Suppose that $T\cup \{e\}$ has a cycle. This cycle cannot contain $e$ as we know that $e$ is not in any cycle in $T\cup \{e\}$. Thus, there must be a cycle in $T\cup \{e\}$ not containing $e$. We can now remove $e$ from $T\cup \{e\}$ and get $T$, which also must contain this cycle, as we didn't touch any edges on this cycle. This is a contradiction, since we know that $T$ doesn't have cycles. $\square$We will show that $T$ never has cycles using induction.Base Case: In the beginning, when $T$ is empty, $T$ has no cycles.Induction step: Let $T$ be the set of edges before our current step of the algorithm. By the induction hypothesis, $T$ has no cycles. Let $T' = T\cup \{e\}$ be the set of edges after the current step of the algorithm. We want to show that $T'$ has no cycles.Consider one step of the algorithm. By definition, Prim's algorithm will choose an edge $e$ such that one endpoint of $e$ is in $X$ and the other is in $V\setminus X$. $(X, V\setminus X)$ is a cut of the graph by definition.Since $V\setminus X$ is the set of vertices not yet used in the tree, there are no edges in $T$ connecting $X$ and $V\setminus X$. This means that $e$ is the only edge in $T'$ connecting the two parts of the cut $(X, V\setminus X)$. Thus, by the Lonely Cut Corollary, $e$ is not in any cycle in $T'$. Therefore, by Lemma 1, $T'$ doesn't have any cycles. $\square$
•  » » 2 months ago, # ^ |   0 This means that e is the only edge in T′ connecting the two parts of the cut (X, V∖X) .I have a doubt about this line. Wouldn't there be a case that there is more than one edge connecting $X$ and $V\setminus X$ before selecting one of them with smallest weight and adding it to $T'$ ? In this case, the lonely cut corollary would not be applicable. Am I thinking in the right direction, or am I missing something?
•  » » » 2 months ago, # ^ |   +6 That never happens.We start with the fact that there are no edges in $T$ connecting $X$ and $V\setminus X$. This follows directly from the fact that $X$ defined as the set of all vertices that are currently connected by any edge. This means that there is no edge that has its endpoint in $V\setminus X$ and thus, no edge between $X$ and $V\setminus X$.Now, consider the tree $T' = T\cup \{e\}$. How is $T'$ different from $T$? $T'$ is otherwise identical to $T$, but $T'$ has one extra edge: $e$.Let's for a moment assume the case you mentioned has happened: $T'$ has two (or more) edges between $X$ and $V\setminus X$. This means that we went from $T$ having $0$ edges between $X$ and $V\setminus X$ to $T'$ having $2$ edges between $X$ and $V\setminus X$, just by adding $1$ new edge and without changing anything else. That just isn't possible.
•  » » » » 2 months ago, # ^ |   +1 Now I get it. Thanks a lot for helping out. This means a lot :)