Claim 5.8 β if S β π has r members then x*(D(S)) = r β 1
ProvedBoundedDegreeST.LowerUpper.claim_5_8Let be a finite simple graph, a forest on edge-disjoint from , a feasible solution of LP-MBDCT with support , and as in the conclusion of Lemma 5.3. For , the members of are its children in the forest of and the supernodes contained in but in no child, and is the set of support edges joining two different members. If has members, then
The identity is what forces at least three fractional edges between the members when (case 2 of Lemma 5.6) and integrality of a single edge when (case 3).
Formalization Note Only feasibility, the forest property of and the conclusion of Lemma 5.3 are assumed, which is all the paper's proof uses. The paper's proof writes for . is the cardinality of the set of members, and the identity is stated in .
import Definitions.Def_BoundedDegreeST_LowerUpper_Tokens
namespace BoundedDegreeST.LowerUpper
/-- SinghβLau, Claim 5.8, p. 669: if `x` is feasible, `(π, T_U, T_W)` is as in
Lemma 5.3 and `S β π` has `r` members (its children in the forest of `π`
and the supernodes inside `S` but in no child), then `x(D(S)) = r β 1`, where
`D(S)` is the set of support edges joining two different members of `S`. -/
theorem claim_5_8 {V : Type*} [Fintype V] [DecidableEq V]
(E F : Finset (Sym2 V)) (A B : V β β€) (U W : Finset V)
(x : Sym2 V β β) (L : Finset (Finset V)) (TU TW : Finset V)
(hE : BoundedDegreeST.PlusOne.SimpleEdges E) (hF : BoundedDegreeST.PlusOne.IsForest F) (hEF : Disjoint E F)
(hfeas : Feasible E A B U W F x)
(hbasis : DefinesBasis E A B U W F x L TU TW)
(S : Finset V) (hS : S β L) :
BoundedDegreeST.PlusOne.edgeSum x (crossing E F x L S) = ((members F L S).card : β) - 1 := by sorry
end BoundedDegreeST.LowerUpper
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.