Lemma 4.10 — R_k outputs a planar multigraph with breakable degree-k and unbreakable degree-4 vertices
ProvedTRVB.PlanarNPC.lemma_4_10complexity-theorygraph-theoryp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let , let be a planar non-alternating directed graph on (no loops, no repeated arcs) with every in- and out-degree equal to , and let be any vertex. Then the output (with as the chosen vertex) is a planar multigraph, and each of its vertices is either breakable of degree or unbreakable of degree .
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.