2
$\begingroup$

According to my instructor, $n\choose 2$ is the maximum number of minimum cuts we can have on a graph. To prove this, he showed the lower bound using an n-cycle graph. To prove the upper bound, he drew the argument from two facts:

  • Probability of finding $i^{th}$ min cut $\geq\frac{2}{n(n-1)}=\frac{1}{n\choose 2}$
  • Event of finding $i^{th}$ min cut is disjoint.

So just adding up the probabilities he proved the upper bound of $n\choose 2$.

Now if we consider a tree, as a graph, with $n$ nodes, then we will be able to conclude $(n-1)$ min cuts which is less than $n\choose 2$ cuts ($ n\geq3)$. Am I missing something here?

$\endgroup$
  • 1
    $\begingroup$ You’re not missing anything. It’s all consistent: $\binom{n}{2}$ is a valid upper bound on $n-1$. $\endgroup$ – Yuval Filmus Jun 18 at 16:49
  • $\begingroup$ Some graphs have $\binom{n}{2}$ minimum cuts. Others have fewer. None have more. $\endgroup$ – Yuval Filmus Jun 18 at 16:50
1
$\begingroup$

"Maximum" here means that no graph can have more than $n \choose 2$ minimum cuts. Obviously, you can come up with graphs (or infinite families of graphs) that have fewer minimum cuts, like say $n-1$. This is less than $n \choose 2$ which is perfectly fine, so this is no contradiction. In other words, the result only means that you can't come up with graphs that have more than the maximum number of minimum cuts.

$\endgroup$
  • $\begingroup$ geez! I am sorry for asking such question. I was so much involved in the Karger's contraction algo analysis that I skipped this very simple thing. I am sorry for wasting your time :/ $\endgroup$ – Shuvam Shah Jun 18 at 18:59
1
$\begingroup$

Some graphs have less than the maximum. This shouldn't be a surprise.

$\endgroup$

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.