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