At most C(n, 2) minimum cuts #
One run of Karger's contraction algorithm outputs one cut (Cslib.Algorithms.Lean.Karger.cutLaw,
the block of the second of the two supervertices it leaves), and each fixed minimum cut {C, Cᶜ}
is that cut with probability at least 2 / (n (n - 1)) = 1 / C(n, 2)
(Cslib.Algorithms.Lean.Karger.two_div_le_cutLaw, Theorem 2.2 of [KS96]). Since each
run outputs one cut, the events for distinct minimum cuts are disjoint, so there are at most
C(n, 2) minimum cuts (card_minCuts_le_choose_two).
Source map ([KS96], author copy dated 6 August 1996): the count of minimum cuts,
attributed in the proof of Theorem 4.4 to Dinitz, Karzanov and Lomonosov (1976), is
card_minCuts_le_choose_two, by the disjointness argument of the proof of Theorem 8.4 (stated
there for α-minimal cuts) applied to Theorem 2.2. The n-cycle attains it, as remarked after
Theorem 2.2; CslibFrontierTests.KargerMinCutCount checks n = 4 and 5.
Scope: weights are natural numbers (Cslib.WeightedCut.IsMultigraph), and the graph is connected
(0 < minCut W₀), without which the count fails (the empty graph on four vertices has seven
non-trivial minimum cuts). A minimum cut {C, Cᶜ} is counted once, by its side C that avoids a
fixed vertex x₀. Not formalized here: the O((2n)^(2α)) bound on α-minimal cuts
(Theorem 8.4), the enumeration and cactus representation of all minimum cuts, and the per-cut
bound for the recursive Karger–Stein algorithm.
Main results #
card_minCuts_le_choose_two: at mostn.choose 2minimum cuts.
References #
At most C(n, 2) minimum cuts [KS96]. A connected multigraph on Fin n has at
most n.choose 2 minimum cuts: at most n.choose 2 vertex sets C with x₀ ∉ C and
cutWeight W₀ C = minCut W₀. Each such C is a non-trivial cut, since 0 < minCut W₀, and each
minimum cut {C, Cᶜ} has exactly one side without x₀. The bound is due to Dinitz, Karzanov and
Lomonosov (1976); this is the proof of [KS96], from the disjointness of the events
that karger outputs each minimum cut.