2
$\begingroup$

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

enter image description here

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Raphael Oct 17 '16 at 8:27
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Wow, that's...strangely simple... $\endgroup$ – FrostyStraw Oct 16 '16 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.