Theorem 1.1 — a minimum-weight odd-splitting edge of the Gomory–Hu cut-tree defines an odd minimum cut-set
ProvedPadbergRao.OddCut.theorem_1_1Let be a finite undirected graph without loops and multiple edges, with edge weights , whose nodes are labelled odd and even such that the set of odd nodes is nonempty and the total label of is even ( even). Let be the Gomory–Hu cut-tree of for all pairs of odd nodes, with edge weights . Call a tree edge odd-splitting if its removal decomposes into two subtrees of odd cardinality. Then:
- has at least one odd-splitting edge; and
- if is an odd-splitting edge of minimum weight among all odd-splitting edges, and is the node set of corresponding to the subtree containing after removing , then is an odd minimum cut-set:
Thus the odd minimum cut-set problem is solved by one Gomory–Hu computation on the odd nodes, followed by a search over the edges of the tree.
Since is even, one of the two subtrees has odd cardinality exactly when the other has, so the statement checks the parity of the -side subtree only.
Formalization Note The cut-tree is IsOddCutTree c odd H π (tree nodes identified with odd nodes; Gomory–Hu minimality for every tree edge); the conclusion IsOddMinCut minimizes over every node set with odd, not only over shores of tree edges. Part 1 ensures that part 2 is not vacuous.
import Mathlib import Definitions.Def_PadbergRao_OddCut_cutCapacity import Definitions.Def_PadbergRao_OddCut_IsOddMinCut import Definitions.Def_PadbergRao_OddCut_IsOddCutTree
namespace PadbergRao.OddCut
/-- Theorem 1.1 (Padberg–Rao 1982, p. 70). Let `G_T` be a Gomory–Hu cut-tree of `G` for the odd
nodes. (1) Some edge of `G_T` splits it into two subtrees of odd cardinality; (2) every such edge
of minimum weight among them defines an odd minimum cut-set of `G`. Since `|V₁|` is even, the
`s`-side subtree has odd cardinality iff the `r`-side one does, so one parity condition suffices. -/
theorem theorem_1_1 {V : Type*} [Fintype V] [DecidableEq V]
(c : V → V → ℝ) (hc_symm : ∀ i j, c i j = c j i) (hc_nonneg : ∀ i j, 0 ≤ c i j)
(odd : Finset V) (hodd_ne : odd.Nonempty) (hodd_even : Even odd.card)
(H : SimpleGraph {v // v ∈ odd}) (π : V → {v // v ∈ odd})
(hT : IsOddCutTree c odd H π) :
(∃ r s : {v // v ∈ odd}, H.Adj r s ∧ Odd (subtree H r s).card) ∧
∀ r s : {v // v ∈ odd}, H.Adj r s → Odd (subtree H r s).card →
(∀ r' s' : {v // v ∈ odd}, H.Adj r' s' → Odd (subtree H r' s').card →
treeEdgeWeight c H π r s ≤ treeEdgeWeight c H π r' s') →
IsOddMinCut c odd (shore H π r s) := by sorry
end PadbergRao.OddCut
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.