Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.2 — ear decompositions extend from a conformal matching covered subgraph

Open
PfaffianRecognition.Recognition.Supplement.lemma_4_2

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorygraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1pfaffian

Let GGG be a matching covered graph and let HHH be a conformal matching covered subgraph of GGG (so G−V(H)G-V(H)G−V(H) has a perfect matching). Then there are t≥0t\ge0t≥0 and subgraphs

H=H0⊆H1⊆⋯⊆Ht=G,H=H_0\subseteq H_1\subseteq\cdots\subseteq H_t=G,H=H0​⊆H1​⊆⋯⊆Ht​=G,

each of them matching covered, such that every Hi+1H_{i+1}Hi+1​ is obtained from HiH_iHi​ by adding either one odd ear of HiH_iHi​ or two vertex-disjoint odd ears of HiH_iHi​. An odd ear of HiH_iHi​ is a path of odd length with both endpoints in V(Hi)V(H_i)V(Hi​), internal vertices outside V(Hi)V(H_i)V(Hi​) and no edge of HiH_iHi​.

This is the ear-decomposition theorem of Lovász and Plummer in the form [LM24, Theorem 11.11]; it drives the induction in the forward direction of Theorem 1.2.

Formalization Note The chain is indexed by Fin (t+1); Ht=GH_t=GHt​=G is the top subgraph; inclusion follows from each step being a supremum with the added ears.

Differences from the source:

  • encoding: arbitrary finite simple graph G → SimpleGraph (Fin N) for every N, vertices in a fixed order; reason: every finite simple graph has such a labelling; no instance is removed
  • reading: matching covered (used, not defined, in the paper) → IsMatchingCovered: connected, at least one edge, every edge in some perfect matching; reason: the standard definition of [LP86]/[LM24] the paper cites; connectivity and an edge are part of it, and without them the statement fails on K1
  • reading: two vertex disjoint odd ears → two odd ears of H_i with no common vertex, endpoints included; reason: the literal reading and the two-ear theorem of Lovász–Plummer; it is the stronger existence claim
Preamble
import Definitions.Def_PfaffianRecognition_Recognition_Supplement_cut_model
Formal statement
namespace PfaffianRecognition.Recognition.Supplement

open PfaffianRecognition.Recognition

/-- Lemma 4.2, p. 12 ([LM24, Theorem 11.11]). An ear decomposition of a matching covered graph
extends from any conformal matching covered subgraph `H`: matching covered subgraphs
`H = H₀ ⊆ ⋯ ⊆ H_t = G`, each obtained from the previous one by adding one odd ear or two vertex
disjoint odd ears. -/
theorem lemma_4_2 {N : ℕ} {G : SimpleGraph (Fin N)} (hG : IsMatchingCovered G)
    (H : G.Subgraph) (hH : IsMatchingCoveredSubgraph H) (hconf : IsConformalSet G H.verts) :
    ∃ (t : ℕ) (Hs : Fin (t + 1) → G.Subgraph),
      Hs 0 = H ∧ Hs (Fin.last t) = ⊤ ∧ (∀ i, IsMatchingCoveredSubgraph (Hs i)) ∧
        ∀ i : Fin t, IsEarStep (Hs i.castSucc) (Hs i.succ) := by sorry

end PfaffianRecognition.Recognition.Supplement
Source
Priyanshu Pant, Ranveer Singh, Pfaffian Recognition is in coRP, STOC 2027 submission #858 (October 2026), Lemma 4.2, p. 12; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/858.pdf

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