Lemma 4.5 — simplifying over a forced arc maintains Hamiltonicity
ProvedTRVB.PlanarNPC.lemma_4_5complexity-theorygraph-theoryp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a finite directed multigraph (loops and repeated arcs allowed) on a finite vertex set , and let be an arc of with . If has out-degree or has in-degree , then is Hamiltonian if and only if the multigraph obtained by simplifying over is Hamiltonian.
Differences from the source:
- generalization: directed graph G → any finite vertex type V and arc list A : List (V × V), loops and repeated arcs allowed; reason: specializes to directed graphs; Theorem 4.7's proof applies the lemma to graphs that simplification has already given loops (INSIGHTS I1)
- encoding: edge (u, v) of G → (u, v) ∈ A together with u ≠ v; reason: contracting a loop is undefined; for a loopless G the condition is automatic
- reading: simplifying G over (u, v) maintains the Hamiltonicity of G → IsHamiltonian A ↔ IsHamiltonian (simplify A u v huv); reason: the proof shows both directions ('G′ is Hamiltonian if and only if G is')
- encoding: Hamiltonian cycle → IsHamCycle: a nonempty vertex set and a set C of arcs with exactly one C-arc out of and one into every vertex, every vertex reaching every vertex along C; IsHamiltonian asserts existence of such a cycle; reason: the standard notion; on one vertex it is a loop, on two vertices a pair of opposite arcs
- encoding: simplifying G over (u, v): the result has one new vertex instead of u and v → simplify A u v huv on the vertex type {x // x ≠ v}, the merged vertex represented by u; it keeps the arcs whose head is not v and whose tail is not u, with v renamed u; reason: the same multigraph up to naming the new vertex
Preamble
import Definitions.Def_TRVB_PlanarNPC_Digraph set_option autoImplicit false
Formal statement
namespace TRVB.PlanarNPC
/-- Lemma 4.5 (p. 10): simplifying over a forced arc maintains Hamiltonicity. -/
theorem lemma_4_5 {V : Type} [Fintype V] [DecidableEq V] (A : List (V × V)) (u v : V)
(huv : u ≠ v) (hA : (u, v) ∈ A) (hdeg : outdeg A u = 1 ∨ indeg A v = 1) :
IsHamiltonian A ↔ IsHamiltonian (simplify A u v huv) := by sorry
end TRVB.PlanarNPC
Source
Demaine & Rudoy, Tree-Residue Vertex-Breaking: a new tool for proving hardness, arXiv:1706.07900v3 (3 May 2018; SWAT 2018, doi:10.4230/LIPIcs.SWAT.2018.32), Lemma 4.5, p. 10 (PDF p. 10). Verbatim: 'Lemma 4.5. If (u, v) is an edge of directed graph G and either u has outdegree 1 or v has indegree 1, then simplifying G over (u, v) maintains the Hamiltonicity of G.' PDF SHA-256: d5f076af211e597d517c4365b4401ca0a6341590adb0a62be78489b9e737fcd7.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.