§2, p. 6, proof of the Theorem (corrected: |V| ≠ 1) — H has a hamilton circuit iff G has a directed postman's tour of weight ≤ k
ProvedRuralPostman.NPC.claim_directedLet be a directed graph on with , and let be the rural postman instance of the directed construction: for each vertex a required arc and a non-required arc , both of weight ; an arc of weight for each arc of ; and . Then
The paper states this equivalence without a size condition and leaves the proof to the reader. It fails for : the one-vertex graph without arcs has no hamilton circuit, yet is a directed postman's tour of weight . For (and trivially for ) the equivalence holds. The equivalence is what makes the construction a reduction from DIRECTED HAMILTON CIRCUIT to DIRECTED 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 Boolean adjacency matrix; a loop of gives an arc of weight . For both sides hold: the hamilton-circuit predicate is vacuous on the empty vertex set and the empty tour is a postman's tour of the empty instance.
Differences from the source:
- correction: the equivalence for every directed graph H → hypothesis v ≠ 1; reason: counterexample: H = ({s}, ∅) has no hamilton circuit, but the tour <s,0> → <s,1> → <s,0> of G has weight 0 ≤ 1 = k (paper.md slip 1)
- 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: a directed graph H = (V,E) → a Bool adjacency matrix adj on Fin v; a loop adj s s = true gives the arc (⟨s,0⟩,⟨s,0⟩) of weight 1; reason: Lean convention for a finite directed graph; for v ≥ 2 loops play no role on either side
- 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 directed cycle visiting each node exactly once → SchedComplexity.NoWait.HasHamiltonCircuit adj (vacuously true for v = 0); reason: for v ≥ 2 a cyclic ordering of all nodes with consecutive arcs is exactly such a cycle; at v = 0 both sides of the equivalence hold
import Mathlib import Definitions.Def_RuralPostman_NPC_Reductions
namespace RuralPostman.NPC
theorem claim_directed {v : ℕ} (adj : Fin v → Fin v → Bool) (hv : v ≠ 1) :
SchedComplexity.NoWait.HasHamiltonCircuit adj ↔ (drpOfGraph adj).RPYes true := by sorry
end RuralPostman.NPC
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.