Number of min-cuts of a graph It can be shown that every graph G has at most $\binom{n}{2}$ min-cuts.
It follows from Karger’s algorithm Analysis.

Is there a different combinatorial proof of this fact? Was this known before Karger’s paper?
An earlier proof that associates to an arbitrary graph G a certain "structural graph" was shown by Dinitz, Karzanov and Lomonosov in 1976 [1].



[1] Dinitz, E. A., Karzanov, A. V., &amp; Lomonosov, M. V. (1976). On the structure of the system of minimum edge cuts in a graph. Issledovaniya po Diskretnoi Optimizatsii, 290-306.