Claim 5.4 — a special supernode contains exactly one active vertex v, with v ∈ T and deg_{E*}(v) = 3
ProvedBoundedDegreeST.LowerUpper.claim_5_4Throughout, 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.4. If a supernode (a component of ) is special, i.e. the excess tokens of its active vertices sum to exactly one, then contains exactly one active vertex , and
The claim identifies the only supernodes that contribute a single excess token in the counting argument.
Formalization Note No supernode is contracted: is a component of in the original graph. The contradiction hypotheses of §5.1 (no 1-edge, no of support degree 2) and " is not a spanning tree" are explicit binders; the claim is false without them.
import Definitions.Def_BoundedDegreeST_LowerUpper_Tokens
namespace BoundedDegreeST.LowerUpper
/-- Singh–Lau, Claim 5.4, p. 668, in the setting of §5.1: `x` is a basic
feasible solution, `F` is not a spanning tree, `(𝓛, T_U, T_W)` is as in
Lemma 5.3, `T = T_U ∪ T_W`, and (contradiction hypotheses) there is no 1-edge
and no `v ∈ U ∪ W` with `deg_{E*}(v) = 2`. A special supernode (excess exactly
one) contains exactly one active vertex `v`, and `v ∈ T` with
`deg_{E*}(v) = 3`. -/
theorem claim_5_4
{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)
(C : Finset V) (hC : IsSpecialSupernode E F x (TU ∪ TW) C) :
∃ v ∈ C, Active E x v ∧ (∀ w ∈ C, Active E x w → w = v) ∧
v ∈ TU ∪ TW ∧ degree (support E x) v = 3 := by sorry
end BoundedDegreeST.LowerUpper
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.