1. How many edges cross a minimum cut in this graph?

 (Image: http://csns.calstatela.edu/download?fileId=4774117)

 0
 1
 2
 3

I got the answer 2 but it's considered as incorrect. Why so? Isn't that the min. cut of this graph? Making a different partition will give a larger quantity of crossing edges. Do we have to use the Random Contraction Algorithm for this?

yxu22 wrote:

The answer is 1 cross edge.

Are you sure you didn't get score when you select the second answer which is 1 cross edge ?

I selected the 3rd option which is 2. Did you solve this problem using the Random Contraction Algorithm?

yxu22 wrote:

The minimum cut is between vertex D and vertex F. So after cut, there is only 1 cross edge.

I don't quite understand how you obtained the min. cut.

vsluong4 wrote:

Yu actually don't use Karger's contraction algorithm to find the min cut.  It asks for the definite min cut and since Karger's contraction algorithm is probabilistic by nature, you'd have to do it ~m² times to get the answer.

 

As for how to find it; in this case it's easy because it's a connected graph and there is a node with a single edge.  There's no way to get better than that for a min cut in this case.  Just put that single node in one set, and everything else in the other- voila only 1 crossing edge, which is minimum.  If you have problems with that, it should've been more of a concern when you were doing a similar question during the class time.

Understood this perfectly. Thanks.