Claim 5.7 β a set S β π with S β V has |Ξ΄(S)| β₯ 2 in the support
ProvedBoundedDegreeST.LowerUpper.claim_5_7counting-argumentiterative-roundingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1spanning-trees
Throughout, 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.7. For every with ,
The claim is used in Claim 5.9 to rule out a special set's cut having fewer than three edges.
Formalization Note In the paper is the root of a subtree of the forest of , so ; the cut is counted in the support .
Preamble
import Definitions.Def_BoundedDegreeST_LowerUpper_Tokens
Formal statement
namespace BoundedDegreeST.LowerUpper
/-- SinghβLau, Claim 5.7, p. 669, in the setting of Β§5.1 (see Claim 5.4): for a
set `S` of the laminar family `π` with `S β V`, at least two edges of the
support `E*` cross `S`. -/
theorem claim_5_7
{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) :
2 β€ (cut (support E x) S).card := by sorry
end BoundedDegreeST.LowerUpper
Source
Singh, Lau, Approximating minimum bounded degree spanning trees to within one of optimal, STOC 2007, p. 669, Claim 5.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.