1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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., & Lomonosov, M. V. (1976). On the structure of the system of minimum edge cuts in a graph. Issledovaniya po Diskretnoi Optimizatsii, 290-306.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.