Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.10 — R_k outputs a planar multigraph with breakable degree-k and unbreakable degree-4 vertices

Proved
TRVB.PlanarNPC.lemma_4_10

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 on 0,…,n−10,\dots,n-10,…,n−1 (no loops, no repeated arcs) with every in- and out-degree equal to 222, and let v^\hat vv^ be any vertex. Then the output M′=Rk(G)M'=R_k(G)M′=Rk​(G) (with v^\hat vv^ as the chosen vertex) is a planar multigraph, and each of its vertices is either breakable of degree kkk or unbreakable of degree 444.

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: planar multigraph (has an embedding in the plane) → IsPlanarMG: a rotation system on the edge ends with #vertex orbits + #face orbits = #edges + 2·#components (genus 0 on every component); reason: Heffter–Edmonds–Ringel rotation principle and Euler's formula: equivalent for finite multigraphs with loops and parallel edges
  • encoding: labeled multigraph → the breakable flags of the TRVB instance rk k n A vhat; reason: the labels are the breakable/unbreakable partition
Preamble
import Definitions.Def_TRVB_PlanarNPC_Rk

set_option autoImplicit false
Formal statement
namespace TRVB.PlanarNPC

/-- Lemma 4.10 (p. 12): the output of `R_k` is planar, with only breakable degree-`k` and
unbreakable degree-4 vertices. -/
theorem lemma_4_10 (k : ℕ) (hk : 4 ≤ k) (n : ℕ) (A : List (Fin n × Fin n))
    (hA : IsP43Instance A) (vhat : Fin n) :
    IsPlanarMG (rk k n A vhat).edges ∧
      ∀ x : Fin (rk k n A vhat).n,
        ((rk k n A vhat).breakable x = true ∧ degree (rk k n A vhat).edges x = k) ∨
          ((rk k n A vhat).breakable x = false ∧ degree (rk k n A vhat).edges x = 4) := 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.10, p. 12 (PDF p. 12). Verbatim: 'Lemma 4.10. The output M′ of Rk is a planar labeled multigraph whose vertices are all breakable with degree k or unbreakable with degree 4.' 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