§2, p. 6, proof of the Theorem — H has a hamilton circuit iff G has a postman's tour of weight ≤ k (undirected, v ≥ 3)
ProvedRuralPostman.NPC.claim_undirectedLet 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 .
Then
Together with the polynomial size of , this equivalence is what makes the construction a reduction from UNDIRECTED HAMILTON CIRCUIT to UNDIRECTED RURAL POSTMAN.
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
- encoding: a hamilton circuit: a cycle visiting each node exactly once → SchedComplexity.NoWait.HasHamiltonCircuit adj: a bijection σ of Fin v with adj (σ i) (σ (i+1 mod v)) = true for all i; reason: for v ≥ 2 a cyclic ordering of all nodes with consecutive arcs is exactly such a cycle
import Mathlib import Definitions.Def_RuralPostman_NPC_Reductions
namespace RuralPostman.NPC
theorem claim_undirected {v : ℕ} (adj : Fin v → Fin v → Bool) (hs : IsSymm adj) (hv : 3 ≤ v) :
SchedComplexity.NoWait.HasHamiltonCircuit adj ↔ (urpOfGraph adj).RPYes false := by sorry
end RuralPostman.NPC
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.