Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.14 — the cycle cover of a TRVB solution is a Hamiltonian cycle

Proved
TRVB.PlanarNPC.lemma_4_14

by Shuze Chen · Nov 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorygraph-theoryp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Let k≥4k\ge4k≥4, let GGG be a planar non-alternating directed graph (no loops, no repeated arcs) with every in- and out-degree equal to 222, let v^\hat vv^ be any vertex and M′=Rk(G)M'=R_k(G)M′=Rk​(G). If SSS is a solution of the TRVB instance M′M'M′, then the corresponding cycle cover, the set of arcs eee with m(e)∉Sm(e)\notin Sm(e)∈/S, is a Hamiltonian cycle of GGG.

Differences from the source:

  • reading: R_k's input: a planar non-alternating graph G whose in- and out-degrees all equal 2 → hypothesis IsP43Instance A: arcs on Fin n, no loop, no repeated arc, every in- and out-degree 2, planar non-alternating; reason: Definition 4.8's input class, with 'graph' read as a directed graph without loops or repeated arcs as in Problem 4.3
  • generalization: pick any specific vertex v̂ of G → the statement holds for every choice vhat : Fin n; reason: specializes to whichever v̂ the algorithm picks
  • encoding: (u1, v), (u2, v) the edges into v, (v, w1), (v, w2) the edges out of v; M built, then m(v̂) removed and two edges added → in-arcs and out-arcs taken in arc-list order; rk lists M′'s edges directly (at v̂: two edges m(f1)–m(f2) and k−3+1 edges m(e1)–m(e2)); m(v) for v ≠ v̂ has index v or v−1, m(A[i]) has index n−1+i; reason: the order of u1/u2 and w1/w2 does not change the multigraph; the listed edges are exactly M′'s
  • encoding: breaking vertices; the resulting multigraph is a tree → breakEnds re-attaches each edge end at a broken vertex to its own new vertex; IsTreeMG = nonempty, connected by walks, and no nonempty closed walk with pairwise distinct edges; reason: the paper's operation on edge ends (a loop at a broken vertex becomes an edge between two new vertices); a loop and two parallel edges are cycles; the empty multigraph is not a tree
  • 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
Preamble
import Definitions.Def_TRVB_PlanarNPC_Rk

set_option autoImplicit false
Formal statement
namespace TRVB.PlanarNPC

/-- Lemma 4.14 (p. 15): that cycle cover is a Hamiltonian cycle. -/
theorem lemma_4_14 (k : ℕ) (hk : 4 ≤ k) (n : ℕ) (A : List (Fin n × Fin n))
    (hA : IsP43Instance A) (vhat : Fin n) (S : Finset (Fin (rk k n A vhat).n))
    (hS : IsSolution (rk k n A vhat) S) :
    IsHamCycle A (Finset.univ.filter (fun i => rkArcVertex k n A vhat i ∉ S)) := 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.14, p. 15 (PDF p. 15). Verbatim: 'Lemma 4.14. Suppose Rk outputs M′ on input G. If there exists a solution to the TRVB problem on M′, then the corresponding cycle cover of G is actually a Hamiltonian cycle.' PDF SHA-256: d5f076af211e597d517c4365b4401ca0a6341590adb0a62be78489b9e737fcd7.
Human review
  • Endorsed by Community (Bot) · Nov 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 10, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me