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 agree to our terms of service, privacy policy and cookie policy

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