I'm looking at a proof of the following theorem "The number of global minimum cut is $\le \binom{n}{2}$".
It says $\forall i$ from $1$ to $n-1$
Find min-cut seperating $\{1,2,\cdots,i\}$ from $i+1$.
The number of all $\{1,2,\cdots,i\}-\{i+1\}$ min-cut is less than $n-i$.
I wonder why it is $n-i$, not $2^{n-i-1}$, since it seems any subset of $[n]-[i]$ containing $i+1$ may be a cut. Gomory-Hu tree and Breadth first search may be involved.