Claim 5.9 — a set S ≠ V with exactly three members, all special, and |D(S)| ≥ 3 is a special set
ProvedBoundedDegreeST.LowerUpper.claim_5_9Throughout, is a finite simple graph, is a forest on with no edge in common with , () and () are integer lower and upper degree bounds on subsets , and is a basic feasible solution of LP-MBDCT with support . The forest is not a spanning tree. By Lemma 5.3 there are , and a laminar family of tight sets defining ; put . As in the proof of Lemma 5.1, assume for contradiction that no edge has and no has .
Claim 5.9. Let with . If has exactly three members , each of them special (a special supernode or a special set in the sense of Definition 5.5), and
then is a special set.
The claim is the step of the induction in Lemma 5.6 that lets a set collecting only three tokens be special.
Formalization Note "Contains exactly three special members" is read as "has exactly three members, and all three are special": the proof computes , which needs the to be all the members, and case 2 of Lemma 5.6 applies the claim in that form. The proof's identity has a misprinted coefficient; the identity that holds is , and the conclusion is unchanged.
import Definitions.Def_BoundedDegreeST_LowerUpper_Tokens
namespace BoundedDegreeST.LowerUpper
/-- Singh–Lau, Claim 5.9, p. 669, in the setting of §5.1 (see Claim 5.4), with
`T = T_U ∪ T_W`: if `S ∈ 𝓛`, `S ≠ V`, `S` has exactly three members, all
three special (each a special supernode or a special set), and `|D(S)| ≥ 3`,
then `S` is a special set (Definition 5.5). -/
theorem claim_5_9
{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)
(hbasic : Basic E A B U W F x) (hnotree : ¬ BoundedDegreeST.PlusOne.IsSpanningTree F)
(hbasis : DefinesBasis E A B U W F x L TU TW)
(hnoone : ∀ e ∈ support E x, x e ≠ 1)
(hnodeg2 : ∀ v ∈ U ∪ W, degree (support E x) v ≠ 2)
(S : Finset V) (hS : S ∈ L) (hSV : S ≠ Finset.univ)
(hthree : (members F L S).card = 3)
(hspecial : ∀ R ∈ members F L S, IsSpecialMember E F x L (TU ∪ TW) R)
(hD : 3 ≤ (crossing E F x L S).card) :
IsSpecialSet E x L (TU ∪ TW) S := by sorry
end BoundedDegreeST.LowerUpper
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.