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.