Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.6 — simplifying maintains the planar non-alternating property

Proved
TRVB.PlanarNPC.lemma_4_6

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

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

Let AAA be a finite directed multigraph (loops and repeated arcs allowed) on a finite vertex set VVV that is planar non-alternating, and let (u,v)(u,v)(u,v) be an arc of AAA with u≠vu\ne vu=v. Then the multigraph obtained by simplifying AAA over (u,v)(u,v)(u,v) is planar non-alternating.

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
  • encoding: planar non-alternating embedding (inward edges in one contiguous section at every vertex) → IsPlanarNonAlternating: a planar rotation system σ with at most one head end d at each vertex whose successor σ d is a tail end; reason: a combinatorial rendering of Definition 4.2 on the planar rotation system
  • 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
  • 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
Preamble
import Definitions.Def_TRVB_PlanarNPC_Digraph

set_option autoImplicit false
Formal statement
namespace TRVB.PlanarNPC

/-- Lemma 4.6 (p. 11): simplifying maintains the planar non-alternating property. -/
theorem lemma_4_6 {V : Type} [Fintype V] [DecidableEq V] (A : List (V × V)) (u v : V)
    (huv : u ≠ v) (hA : (u, v) ∈ A) (hpna : IsPlanarNonAlternating A) :
    IsPlanarNonAlternating (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.6, p. 11 (PDF p. 11). Verbatim: 'Lemma 4.6. If (u, v) is an edge of planar non-alternating directed graph G, then simplifying G over (u, v) maintains the planar non-alternating property of G.' 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