Lemma 5.6 β every S β π keeps at least three tokens, and exactly three only if S is a special set or S = V
ProvedBoundedDegreeST.LowerUpper.lemma_5_6Throughout, 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 .Every active vertex holds tokens.
Lemma 5.6. For every , the tokens of the vertices of can be distributed so that every vertex of and every set of strictly inside gets at least two tokens and gets at least three; and gets exactly three only if is a special set or . In counting form:
and implies that is a special set or .
The lemma is the counting step that, together with the rank count of Lemma 5.3, proves Lemma 5.1.
Formalization Note A distribution of fungible tokens with these lower bounds exists exactly when the surplus is at least the root's share, so "can distribute" is rendered as the counting inequality, and "gets exactly three tokens" as surplus equal to three. The rooted subtree is identified by its root .
import Definitions.Def_BoundedDegreeST_LowerUpper_Tokens
namespace BoundedDegreeST.LowerUpper
/-- SinghβLau, Lemma 5.6, p. 669, as a counting statement, in the setting of
Β§5.1 (see Claim 5.4), with `T = T_U βͺ T_W`. For every `S β π`, the
`β_{v β S} deg_{E*}(v)` tokens of the vertices of `S` cover two tokens for every
vertex of `T β© S`, two for every member of `π` strictly inside `S`, and at
least three for `S`; and the root gets exactly three only if `S` is a special
set or `S = V`. -/
theorem lemma_5_6
{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) :
3 β€ surplus E x L (TU βͺ TW) S β§
(surplus E x L (TU βͺ TW) S = 3 β
IsSpecialSet E x L (TU βͺ TW) S β¨ S = Finset.univ) := by sorry
end BoundedDegreeST.LowerUpper
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.