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

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)?

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Oct 17, 2016 at 8:27

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)$.