Number of minimum cuts in a graph

Question

Situation :

I started watching Algorithm Lectures from Stanford University (Corsera). I stuck on one video lecture(https://www.coursera.org/lecture/algorithms-divide-conquer/counting-minimum-cuts-96RUg). In the lecture the professor is proving largest number of minimum cut in a graph.

My Problem :

To prove largest number of minimum cut in a graph. Prof. first stared proving Lower Bound. To get a lower bound he took a cyclic graph. My confusion is why he took cyclic graph?

My way of Thinking :

To get a lower bound we need to select the best case input (like for selection sort best case input will be an sorted array) and here Prof. was selected cyclic graph as an input but it doesn't seems to be the best case input. Like if we choose a star (https://en.wikipedia.org/wiki/Star_(graph_theory)) we could have easily get a lower bound which is n-1.

Answer 1

I don't know the lecture you are referring to, but I do know the topic.

In this case "lower bound" is meant in an existential sense. That is, for every sufficiently large $n$, there exists a graph $G$ on $n$ nodes such that the number of minimum cuts in $G$ is $\binom{n}{2}$. In particular $G$ is a cycle on $n$ nodes.

The easiest way to see why this definition of lower bound is interesting is to think of upper bounds first. It is possible to show that the number of minimum cuts in any graph with $n$ nodes is at most $\binom{n}{2}$. Then one natural question is whether this upper bound is tight or whether it can be improved.

Your lower bound answers the above question: it is not possible to prove any upper bound smaller than $\binom{n}{2}$ since there is always at least one graph on $n$ nodes for which there are at least $\binom{n}{2}$ minimum cuts.

Note that, in this sense, the lower bound of $n-1$ that you can obtain by considering a star is a worse lower bound than the one you obtain by considering a cycle.

To summarize: an existential lower bound of $f(n)$ means that, in general, there can be no better upper bound than $f(n)$. Often times you'll find that lower bounds are expressed using asymptotic notation. A lower bound of $\Omega(f(n))$ means that there can be no upper bound better than $c f(n)$ for some constant $c>0$.