§2, p. 6, proof of the Theorem — a hamilton circuit of H gives a postman's tour of G traversing R twice and v arcs of A−R once, of weight v = k
ProvedRuralPostman.NPC.claim_undirected_forwardLet 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 .
If has a hamilton circuit, then has an undirected postman's tour that
- traverses every arc of exactly twice;
- traverses exactly arcs of , each exactly once, and no other arc of ;
- has total weight
This is the "if" direction of the equivalence on which the undirected reduction rests.
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. Clause 2 is stated as: the number of traversals of arcs outside is , and each arc outside is traversed at most once.
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
- encoding: "traversing all arcs in R exactly twice and v arcs in A-R exactly once" → every required arc occurs in exactly 2 traversals; exactly v traversals are of non-required arcs; every non-required arc occurs in at most 1 traversal; reason: the same condition expressed by counting traversals
import Mathlib import Definitions.Def_RuralPostman_NPC_Reductions
namespace RuralPostman.NPC
theorem claim_undirected_forward {v : ℕ} (adj : Fin v → Fin v → Bool) (hs : IsSymm adj)
(hv : 3 ≤ v) (hH : SchedComplexity.NoWait.HasHamiltonCircuit adj) :
∃ τ : List (urpOfGraph adj).Traversal, (urpOfGraph adj).IsTour false τ ∧
(∀ e, (urpOfGraph adj).IsRequired e → τ.countP (fun t => t.1 = e) = 2) ∧
τ.countP (fun t => ¬ (urpOfGraph adj).IsRequired t.1) = v ∧
(∀ e, ¬ (urpOfGraph adj).IsRequired e → τ.countP (fun t => t.1 = e) ≤ 1) ∧
(urpOfGraph adj).tourWeight τ = v := by sorry
end RuralPostman.NPC
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.