p. 17, after Proposition 4.5 — contracting a Figure 7 sequence gives a tour on n − 4 vertices at least 4 cheaper
ProvedCircletTSP.Facet.contraction_stepLet be a multiple of , , labels . Let be a Hamiltonian cycle on that contains one of the two edge sequences of Figure 7,
with . Let be obtained by contraction: delete , replace the five edges by , and relabel every other vertex as . Then is a Hamiltonian cycle on and
By Claims 4.1 and 4.2, every structure A, B1, B2 can be brought to one of these two sequences, so this is the statement that a tour with any of the structures of Figure 4 contracts to a tour on four fewer vertices that is at least cheaper, which completes the proof of Lemma 3.4.
Formalization Note is not printed in this sentence; the proof of Theorem 3.1 derives it from Claim 3.2 ("By Claim 3.2, ", p. 10), and for there is no tour on vertices. The contracted cycle is given explicitly as the vector contract n (tourVec π) j k on Fin (n - 4) and the statement asserts that it is the incidence vector of some ordering, so the conclusion is about the specific contracted tour, not merely some cheap tour.
import Mathlib import Definitions.Def_MetricTSP_tour_vector import Definitions.Def_CircletTSP_Facet_Setting
namespace CircletTSP.Facet
/-- The contraction step (p. 17, after Proposition 4.5): if a Hamiltonian cycle on `n ≥ 8`
vertices contains one of the two edge sequences of Figure 7, `{j, 1}, {1, 2}, {2, d + 2},
{d + 2, d + 1}, {d + 1, k}` or `{j, d + 2}, {d + 2, 2}, {2, 1}, {1, d + 1}, {d + 1, k}`
(1-based labels, `d = n / 2`), then contracting it (p. 14) yields a Hamiltonian cycle on
`n - 4` vertices whose circlet cost is at least `4` smaller. -/
theorem contraction_step (n : ℕ) (hn : 8 ≤ n) (h4 : 4 ∣ n) (π : Equiv.Perm (Fin n)) (j k : ℕ)
(hj : j ∈ keptLabels n) (hk : k ∈ keptLabels n) (hchain : ChainOne π j k ∨ ChainTwo π j k) :
(∃ σ : Equiv.Perm (Fin (n - 4)),
MetricTSP.tourVec σ = contract n (MetricTSP.tourVec π) j k) ∧
circletForm (n - 4) (contract n (MetricTSP.tourVec π) j k) + 4 ≤
circletForm n (MetricTSP.tourVec π) := by sorry
end CircletTSP.Facet
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.