# Expected Linear time Minimum Spanning Tree algorithm

I am trying to understand the proposed "Randomized Linear-Time Algorithm to Find MST".

My findings: I have read and search almost every available resource( main paper, wiki, reports on paper, lecture on paper ) but not getting any clue regarding my confusion.

Question: In the original paper Section 3: The Algorithm "Step 2" says "In the contracted graph, choose a subgraph H by selecting each edge independently with probability 1/2."

If I have 6 vertexes with 14 edges. And if I choose 7 edges with probability 1/2 then there might be some isolated vertex. In that case, what will happen to that isolated vertex?

• What do you mean by "choose 7 edges with probability 1/2"? You choose each edge with probability 1/2. You might choose 0 edges or 14 edges. The probability to choose exactly 7 edges is only 21%. – Yuval Filmus Dec 4 '17 at 8:52
• I have lack knowledge of probability. So, I misinterpret that part. Let me rephrase what I understood. "Choosing anything with probability 1/2 means, either I will choose it, or I will not choose it. And chances of choosing it 1/2 also chances of not choosing it 1/2." In other cases, if it says "Choosing anything with probability 1/4 means, either I will choose it, or I will not choose it. And chances of choosing it 1/4 and chances of not choosing it 3/4." Please let me know if I am correct. – Choudhury A. M. Dec 4 '17 at 13:45
• It is impossible to understand randomized algorithms without a good grasp of elementary probability theory. I suggest you learn enough probability to be able to calculate the probability that exactly 7 edges are chosen, and only then proceed in your efforts to understand this particular algorithm. – Yuval Filmus Dec 4 '17 at 14:03

Nothing in particular happens if there is an isolated vertex. The algorithm is correct even if $H$ consists of no edges, or if it consists of all edges. The algorithm proceeds by finding a minimum spanning forest on $H$, and using it to prune the contracted graph. IF $H$ consists of no edges, then nothing is pruned, but the algorithm remains correct - this only affects the running time.