Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Cut reversal DXD^XDX, strong connectivity, matching covered and conformal subgraphs, oddly oriented cycles, odd ears

Definition
PfaffianRecognition_Recognition_Supplement_cut_model

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 finite simple graph on the ordered vertex set {0,…,N−1}\{0,\ldots,N-1\}{0,…,N−1} and let DDD be an orientation of GGG (one direction on each edge, none on a non-edge), as in the published graph model.

  1. Cut reversal. For a vertex set X⊆V(G)X\subseteq V(G)X⊆V(G), the cut ∂(X)\partial(X)∂(X) consists of the edges with exactly one endpoint in XXX. The orientation DXD^XDX reverses every edge of ∂(X)\partial(X)∂(X) and keeps every other edge:
DX(i,j)  ⟺  (∣{i,j}∩X∣=1 and D(j,i)) or (∣{i,j}∩X∣≠1 and D(i,j)).D^X(i,j)\iff\bigl(|\{i,j\}\cap X|=1\text{ and }D(j,i)\bigr)\ \text{or}\ \bigl(|\{i,j\}\cap X|\ne1\text{ and }D(i,j)\bigr).DX(i,j)⟺(∣{i,j}∩X∣=1 and D(j,i)) or (∣{i,j}∩X∣=1 and D(i,j)).

DXD^XDX is again an orientation of GGG; XXX ranges over all subsets, ∅\emptyset∅ and V(G)V(G)V(G) included. 2. Strong connectivity. An orientation is strongly connected when every vertex is reachable from every vertex by a directed path (the published digraph predicate applied to the arcs of the orientation). 3. Matching covered. A subgraph HHH of GGG is matching covered when it is connected, has at least one edge, and every edge of HHH lies in a perfect matching of HHH (a set of edges of HHH covering every vertex of HHH exactly once). GGG itself is matching covered when the same holds with the perfect matchings of GGG. 4. Conformal. A vertex set SSS, or a subgraph with vertex set SSS, is conformal when G−SG-SG−S has a perfect matching. 5. Oddly oriented. A closed walk v0v1⋯vℓ−1v0v_0v_1\cdots v_{\ell-1}v_0v0​v1​⋯vℓ−1​v0​ is oddly oriented in DDD when an odd number of its edges are directed along the traversal, i.e. D(vi,vi+1)D(v_i,v_{i+1})D(vi​,vi+1​) for an odd number of iii; for an even cycle this parity does not depend on the direction of traversal. 6. Odd ears and ear steps. An odd ear of a subgraph HHH is a path of odd length whose endpoints lie in V(H)V(H)V(H), whose internal vertices lie outside V(H)V(H)V(H), and none of whose edges is an edge of HHH. H′H'H′ is obtained from HHH by an ear step when H′=H∪PH'=H\cup PH′=H∪P for one odd ear PPP of HHH, or H′=H∪P∪QH'=H\cup P\cup QH′=H∪P∪Q for two odd ears P,QP,QP,Q of HHH with no common vertex.

These are the objects of §1 (p. 4) and §4 (p. 12) used in Theorem 1.2 and Lemmas 4.1–4.3.

Formalization Note Cycles, paths and ears are Mathlib walks (IsCycle, IsPath); subgraphs are G.Subgraph with ⊤ for GGG; adding an ear is the supremum with the ear's subgraph. Matching covered is not defined in the paper; the standard definition of Lovász–Plummer and Lucchesi–Murty is used.

Definition code
import Mathlib
import Definitions.Def_PfaffianRecognition_Recognition_graph_model
import Definitions.Def_FASTournament_IsStrong

noncomputable section

namespace PfaffianRecognition.Recognition.Supplement

open PfaffianRecognition.Recognition

/-- §1, p. 4: `D^X`, the orientation obtained from `D` by reversing every edge of the cut
`∂(X)`, i.e. every edge with exactly one endpoint in `X`. Edges inside `X` or inside its
complement keep their direction. `X` is an arbitrary vertex set, `∅` and all of `V(G)` included. -/
def cutReversal {N : ℕ} {G : SimpleGraph (Fin N)} (D : Orientation G) (X : Set (Fin N)) :
    Orientation G :=
  ⟨fun i j => (¬ (i ∈ X ↔ j ∈ X) ∧ D.val j i) ∨ ((i ∈ X ↔ j ∈ X) ∧ D.val i j), by
    obtain ⟨hD₁, hD₂⟩ := D.property
    refine ⟨fun u v h => ?_, fun u v h => ?_⟩
    · rcases h with ⟨_, h⟩ | ⟨_, h⟩
      · exact (hD₁ v u h).symm
      · exact hD₁ u v h
    · obtain ⟨h₁, h₂⟩ := hD₂ u v h
      have hx : (v ∈ X ↔ u ∈ X) ↔ (u ∈ X ↔ v ∈ X) := Iff.comm
      show (((¬ (u ∈ X ↔ v ∈ X) ∧ D.val v u) ∨ ((u ∈ X ↔ v ∈ X) ∧ D.val u v)) ∨
          ((¬ (v ∈ X ↔ u ∈ X) ∧ D.val u v) ∨ ((v ∈ X ↔ u ∈ X) ∧ D.val v u))) ∧
        ¬ (((¬ (u ∈ X ↔ v ∈ X) ∧ D.val v u) ∨ ((u ∈ X ↔ v ∈ X) ∧ D.val u v)) ∧
          ((¬ (v ∈ X ↔ u ∈ X) ∧ D.val u v) ∨ ((v ∈ X ↔ u ∈ X) ∧ D.val v u)))
      rw [hx]
      by_cases hc : (u ∈ X ↔ v ∈ X) <;> simp only [hc, not_true_eq_false, not_false_eq_true,
        true_and, false_and, false_or, or_false] <;> tauto⟩

/-- §1, p. 4: an orientation is strongly connected when every vertex is reachable from every
vertex by a directed path, i.e. the published digraph strong-connectivity predicate applied to the
arc relation of the orientation on all of `Fin N`. -/
def IsStronglyConnected {N : ℕ} {G : SimpleGraph (Fin N)} (D : Orientation G) : Prop :=
  FASTournament.IsStrong (⟨D.val⟩ : Digraph (Fin N))

/-- A perfect matching of a subgraph `H` of `G`: a set of edges of `H` covering every vertex of
`H` exactly once. For `H = ⊤` this is the published `IsPerfectMatchingEdges G`. -/
def IsSubgraphPerfectMatching {N : ℕ} {G : SimpleGraph (Fin N)} (H : G.Subgraph)
    (M : Finset G.edgeSet) : Prop :=
  (∀ e ∈ M, (e : Sym2 (Fin N)) ∈ H.edgeSet) ∧
    ∀ v ∈ H.verts, ∃! e, e ∈ M ∧ v ∈ (e : Sym2 (Fin N))

/-- Matching covered subgraph (standard notion of Lovász–Plummer, used on pp. 3–4, 12–14):
`H` is connected, has at least one edge, and every edge of `H` lies in some perfect matching
of `H`. -/
def IsMatchingCoveredSubgraph {N : ℕ} {G : SimpleGraph (Fin N)} (H : G.Subgraph) : Prop :=
  H.Connected ∧ H.edgeSet.Nonempty ∧
    ∀ e ∈ H.edgeSet, ∃ M : Finset G.edgeSet, IsSubgraphPerfectMatching H M ∧
      ∃ f ∈ M, (f : Sym2 (Fin N)) = e

/-- A matching covered graph: connected, with at least one edge, every edge in a perfect
matching (`IsPerfectMatchingEdges`). -/
def IsMatchingCovered {N : ℕ} (G : SimpleGraph (Fin N)) : Prop :=
  G.Connected ∧ G.edgeSet.Nonempty ∧
    ∀ e : G.edgeSet, ∃ M : Finset G.edgeSet,
      MulmuleyVV.Matching.IsPerfectMatchingEdges G M ∧ e ∈ M

/-- p. 3: a vertex set `S` is conformal when `G − S` has a perfect matching: some set of edges of
`G`, none meeting `S`, covers every vertex outside `S` exactly once. A subgraph is conformal when
its vertex set is. -/
def IsConformalSet {N : ℕ} (G : SimpleGraph (Fin N)) (S : Set (Fin N)) : Prop :=
  ∃ M : Finset G.edgeSet, (∀ e ∈ M, ∀ v ∈ (e : Sym2 (Fin N)), v ∉ S) ∧
    ∀ v, v ∉ S → ∃! e, e ∈ M ∧ v ∈ (e : Sym2 (Fin N))

/-- Number of edges of a closed walk `v₀ v₁ ⋯ v₀` directed along its direction of traversal
(darts `vᵢ → vᵢ₊₁` with `D vᵢ vᵢ₊₁`). -/
def forwardCount {N : ℕ} {G : SimpleGraph (Fin N)} (D : Orientation G) {u v : Fin N}
    (p : G.Walk u v) : ℕ := by
  classical
  exact (p.darts.filter fun d => D.val d.fst d.snd).length

/-- p. 3: an (even) cycle is oddly oriented in `D` when an odd number of its edges are
directed along its direction of traversal. -/
def IsOddlyOriented {N : ℕ} {G : SimpleGraph (Fin N)} (D : Orientation G) {u : Fin N}
    (p : G.Walk u u) : Prop :=
  Odd (forwardCount D p)

/-- p. 12: an odd ear of a subgraph `H`: a path of odd length with both endpoints in `V(H)`, all
other (internal) vertices outside `V(H)`, and no edge in `H`. -/
def IsOddEar {N : ℕ} {G : SimpleGraph (Fin N)} (H : G.Subgraph) {a b : Fin N}
    (p : G.Walk a b) : Prop :=
  p.IsPath ∧ Odd p.length ∧ a ∈ H.verts ∧ b ∈ H.verts ∧
    (∀ v ∈ p.support, v ≠ a → v ≠ b → v ∉ H.verts) ∧
    ∀ e ∈ p.edges, e ∉ H.edgeSet

/-- p. 12: `H'` is obtained from `H` by adding one odd ear, or two vertex-disjoint odd ears
(no common vertex, endpoints included); the added ears contribute their vertices and edges. -/
def IsEarStep {N : ℕ} {G : SimpleGraph (Fin N)} (H H' : G.Subgraph) : Prop :=
  (∃ (a b : Fin N) (p : G.Walk a b), IsOddEar H p ∧ H' = H ⊔ p.toSubgraph) ∨
  (∃ (a b c d : Fin N) (p : G.Walk a b) (q : G.Walk c d),
      IsOddEar H p ∧ IsOddEar H q ∧ (∀ v ∈ p.support, v ∉ q.support) ∧
      H' = H ⊔ p.toSubgraph ⊔ q.toSubgraph)

end PfaffianRecognition.Recognition.Supplement
Source
Priyanshu Pant, Ranveer Singh, Pfaffian Recognition is in coRP, STOC 2027 submission #858 (October 2026), §1, pp. 3–4 (conformal subgraph, oddly oriented, strongly connected, ∂(X), D^X); §4, p. 12 (odd ear, ear decomposition); matching covered as in [LP86], [LM24]; 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