Claim 4.5 — vertices with one excess token
ProvedBoundedDegreeST.PlusOne.claim_4_5iterative-roundinglinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1spanning-trees
In the contradiction setting of Lemma 4.1, let be a basic feasible LP solution and let be its laminar basis. Suppose no supported edge has value and every has . For an active vertex , define its excess tokens as when , and as otherwise. If it has exactly one excess token, then
This restricts the low-token cases in the counting lemma.
Formalization Note The preterminal and contradiction assumptions from the surrounding proof are explicit hypotheses.
Preamble
import Definitions.Def_BoundedDegreeST_PlusOne_Algorithm
Formal statement
namespace BoundedDegreeST.PlusOne
/-- Singh–Lau, Claim 4.5, p. 667. -/
theorem claim_4_5 {V : Type*} [Fintype V] [DecidableEq V]
(I : Instance V) (x : Sym2 V → ℝ)
(L : Finset (Finset V)) (T : Finset V) (v : V)
(hvalid : Valid I) (hbasic : Basic I.E I.B I.W I.F x)
(hnotree : ¬ IsSpanningTree I.F)
(hbasis : DefinesBasis I.E I.B I.W I.F x L T)
(hnoone : ∀ e ∈ support I.E x, x e ≠ 1)
(hnosmall : ∀ w ∈ I.W, (degree (support I.E x) w : ℤ) > I.B w + 1)
(hactive : 0 < degree (support I.E x) v)
(hone : excessTokens (support I.E x) T v = 1) :
(v ∉ T ∧ degree (support I.E x) v = 1) ∨
(v ∈ T ∧ degree (support I.E x) v = 3 ∧ I.B v = 1) := by sorry
end BoundedDegreeST.PlusOne
Source
Singh, Lau, Approximating minimum bounded degree spanning trees to within one of optimal, STOC 2007, p. 667, Claim 4.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.