# How can maximum number of minimum cuts of a graph be exactly $n \choose 2$?

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?

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

"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.