Proposition 10.3: for every tour
ProvedSupplyChainTheory.two_matching_cut_formoperations-researchpolyhedral-combinatoricstraveling-salesmanvalid-inequalities
Proposition 10.3. For any handle and teeth satisfying the conditions of Theorem 10.2, every tour through satisfies
the number of tour edges leaving the handle plus the numbers leaving each tooth is at least . The book's proof: a tooth whose two nodes are joined by a tour edge has two edges leaving it, any other tooth four; each such joined tooth contributes an edge leaving ; and the number of edges leaving is even while is odd, which forces one extra edge when every tooth is joined.
Preamble
import Definitions.Def_SupplyChainTheory_tsp
Formal statement
open Classical
namespace SupplyChainTheory
theorem two_matching_cut_form {n s : ℕ} (hn : 3 ≤ n) (τ : Equiv.Perm (Fin n))
(H : Finset (Fin n)) (T : Fin s → Finset (Fin n)) (hcomb : IsComb H T)
(hteeth : ∀ k, (T k).card = 2) :
3 * s + 1 ≤ edgesLeaving τ H + ∑ k, edgesLeaving τ (T k) := by sorry
end SupplyChainTheory
Source
Lawrence V. Snyder and Zuo-Jun Max Shen, Fundamentals of Supply Chain Theory, 2nd ed., Wiley 2019, DOI 10.1002/9781119584445, pp. 414-415, Sect. 10.3.3, Proposition 10.3, Eq. (10.16)-(10.19), and its proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.