Doubt on Karger's Algorithm for Min-Cuts

Question

I am learning Karger's algorithm for Min-Cuts.I have been solving 1 problem on it. The first part of the problem asks us to run Karger's Algorithm on a given graph. I have no problem doing that. My doubt is in the 2nd part of the question.

2nd part of the question asks to find the probability of contracting 2 vertices in each step of the algorithm.

My approach is that - Since contracting 2 vertices is equivalent to contracting an edge, because every time we contract an edge, we are contracting 2 vertices into 1, so to answer the question, I can just find the number of edges at each step 'i' in my algorithm and and find the probability.

For example, if the number of edges in step 'i' of my algorithm run is 5, I can say that Probability(Contracting 2 vertices) = 1/5. since we can pick anyone of the 5 edges.

Please help me out in finding if my approach is right or wrong.

Answer 1

The approach is right, however, you are missing a little detail. Karger's algorithm runs on multigraphs. Hence, two vertices can have more than one edge between them and hence, the probability of contracting them the disjoint sum of the probability of contracting any of the edges between them which is the number of edges between them over the total number of edges in the graph.