§2, p. 6, proof of the Theorem — a postman's tour of G of weight ≤ k traverses k arcs of A−R exactly once
ProvedRuralPostman.NPC.claim_undirected_countLet be an undirected graph on with , and let (arcs , required arcs , weight , threshold ) be the rural postman instance of the undirected construction: a required pendant arc of weight for each vertex , and an arc of weight for each edge of .
Let be any undirected postman's tour of with weight at most . Then traverses arcs of exactly times in total, and no arc of is traversed twice:
In other words, traverses arcs of exactly once each.
This counting step is the core of the "only if" direction of the undirected equivalence.
Formalization Note Nodes are 0-based: is Fin v, and is Fin (v + v) with = Fin.castAdd v s and = Fin.natAdd v s. A tour is a list of traversals (arc index, direction); IsRequired e says that arc lies in , and List.countP counts traversals. is a symmetric Boolean adjacency matrix.
Differences from the source:
- encoding: V a set of v nodes; N = V × {0,1} → V = Fin v (0-based); ⟨s,0⟩ = Fin.castAdd v s and ⟨s,1⟩ = Fin.natAdd v s in Fin (v + v); reason: Lean convention; the same instances up to relabelling
- encoding: an undirected graph H = (V,E) → a Bool adjacency matrix adj on Fin v with IsSymm adj (diagonal ignored); reason: Lean convention for a finite undirected graph; loops play no role in a hamilton circuit on ≥ 3 nodes
- encoding: {(<s,0>,<t,0>) | (s,t) ∈ E} → one arc (⟨s,0⟩,⟨t,0⟩) of weight 1 for each pair s < t with adj s t = true; reason: each undirected edge of H gives one arc of G (paper.md reading 6)
- reading: a postman's tour is an "undirected (directed) cycle traversing each arc in R at least once" → a closed walk: a cyclic list of arc traversals in which nodes and arcs may repeat; the empty list is allowed; reason: the paper's own tour traverses each arc of R twice, so "cycle" means closed walk (paper.md reading 3); the empty tour matters only when R = ∅, where every reading gives weight 0
- reading: "such a tour traverses at most k times an arc from A-R. … it traverses k arcs from A-R exactly once" → the number of traversals of non-required arcs equals v (= k), and every non-required arc occurs in at most 1 traversal; reason: the conclusion "k arcs from A-R exactly once" in counting form; the intermediate bound "at most k" is implied
import Mathlib import Definitions.Def_RuralPostman_NPC_Reductions
namespace RuralPostman.NPC
theorem claim_undirected_count {v : ℕ} (adj : Fin v → Fin v → Bool) (hs : IsSymm adj)
(hv : 3 ≤ v) (τ : List (urpOfGraph adj).Traversal) (hτ : (urpOfGraph adj).IsTour false τ)
(hw : (urpOfGraph adj).tourWeight τ ≤ (urpOfGraph adj).k) :
τ.countP (fun t => ¬ (urpOfGraph adj).IsRequired t.1) = v ∧
∀ e, ¬ (urpOfGraph adj).IsRequired e → τ.countP (fun t => t.1 = e) ≤ 1 := by sorry
end RuralPostman.NPC
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.