[Solved]: Karger's algorithm: why does every vertex have degree at least the number of edges crossing a min cut?

Problem Detail: 

I'm currently watching a video on the analysis of Krager's Algorithm, and I am confused about something.

The analysis goes as follows:

Fix a min cut $(A,B)$.

Let $k$ = # of edges crossing $(A,B)$ , these edges will be called $F$

Let $S_{i}$ be the event that an edge of $F$ is contracted in iteration $i$.

For the first iteration, $\Pr [S_i] = \frac{\text{# of crossing edges}}{\text{# of edges}}=\frac{k}{m}$,

where $k$ is the number of crossing edges, and $m$ is the total number of edges.

Here's where I get confused:

Observation: The degree of each vertex is at least k

Reason: Each vertex v defines a cut $\left( \{v\}, V - \{v\} \right)$

I don't really understand. The reason given for his observation doesn't make much sense to me. Why would the degree of each vertex be at least the number of edges crossing our min cut (A,B)?

Asked By : FrostyStraw

Answered By : Ariel

You pretty much have the answer in front of you.

For any vertex $v$, the cut $\left(\left\{v\right\},V\setminus\left\{v\right\}\right)$ has $\text{deg}(v)$ crossing edges.

If there exists a vertex $v$ with degree $<k$, then its corresponding cut has less than $k$ crossing edges, contradicting the minimality of $(A,B)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/64694

 Ask a Question

 Download Related Notes/Documents