AFTD Auto-Formalizing Theoretical Domains

orientation_perfect_matching_sign_eq_one_or_neg_one

theoremverified

If D is an orientation of a simple graph G on Fin n (is_graph_orientation G D) and M is a perfect matching of G, then orientation_perfect_matching_sign D M is 1 or -1.

Statement

theorem orientation_perfect_matching_sign_eq_one_or_neg_one {n : ℕ} (G : SimpleGraph (Fin n))
    (D : Digraph (Fin n)) (hD : is_graph_orientation G D) (M : G.Subgraph)
    (hM : M.IsPerfectMatching) :
    orientation_perfect_matching_sign D M = 1 ∨ orientation_perfect_matching_sign D M = -1
Source
arXiv:2611.00468 (The symbolic pfaffian method I), Section 1.1 (the sign of a perfect matching is ±1)
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • orientation_perfect_matching_signFor n : ℕ, a simple graph G : SimpleGraph (Fin n) (implicit), a digraph D : Digraph (Fin n) and a subgraph M : G.Subgraph, the integer…
  • is_graph_orientationA digraph D is an orientation of a simple graph G if every edge of G is assigned exactly one direction in D, and non-adjacent pairs in G…
Used by 1

The proof, explained

A perfect matching M pairs each vertex v with a unique partner p(v), making p an involution. Since D is an orientation of G, for each matched pair {v, p(v)}, exactly one of the directed edges (v, p(v)) or (p(v), v) belongs to D. The vertices v whose matching edge is directed as v → p(v) form a subset T of size n / 2 that partitions the vertex set with p(T). Interleaving the elements of T at even indices and their partners at odd indices yields a permutation π whose consecutive pairs are directed matching edges, which ensures by definition that the sign of the matching is 1 or -1.

  1. Each vertex v has a unique neighbor p(v) in the matching M, and the resulting partner map p is an involution (hence injective).

    Since M is a perfect matching, every vertex v in Fin n has a unique adjacent vertex in M. We choose a function p : Fin n → Fin n such that v and p(v) are adjacent in M for all v. By symmetry of adjacency, p(v) is adjacent to v, so by uniqueness of the neighbor of p(v), p(p(v)) = v. Since p ∘ p is the identity, p is injective.

    lines 5–10

      classical
      -- the partner map
      have hex : ∀ v, ∃! w, M.Adj v w := fun v => hM.1 (hM.2 v)
      choose p hp huniq using hex
      have hpp : ∀ v, p (p v) = v := fun v => (huniq (p v) v (hp v).symm).symm
      have hpinj : Function.Injective p := fun a b h => by rw [← hpp a, h, hpp b]
  2. Defining T as the set of vertices whose matching edge is directed towards their partner in D, exactly one of {v, p(v)} belongs to T for every vertex v.

    Let T be the set of vertices v with a directed edge v → p(v) in D. Because the matching edge {v, p(v)} belongs to G and D is an orientation of G, exactly one of the directed edges (v, p(v)) or (p(v), v) belongs to D. Since p(p(v)) = v, p(v) ∈ T is equivalent to (p(v), v) ∈ D, which is the negation of (v, p(v)) ∈ D, so v ∈ T ↔ p(v) ∉ T.

    lines 11–18

    uses Finset.mem_filter, Finset.mem_univ, true_and

      set T : Finset (Fin n) := Finset.univ.filter (fun v => D.Adj v (p v)) with hT
      have hxor : ∀ v, v ∈ T ↔ p v ∉ T := by
        intro v
        have hG : G.Adj v (p v) := M.adj_sub (hp v)
        have h1 := (hD.1 v (p v)).mpr hG
        have h2 := hD.2 v (p v)
        simp only [hT, Finset.mem_filter, Finset.mem_univ, true_and, hpp]
        tauto
  3. The sets T and p(T) partition Fin n, so 2 * |T| = n.

    Every vertex v belongs to either T or p(T), but not both: if a ∈ T and a = p(b) with b ∈ T, then by the previous equivalence p(b) ∉ T, a contradiction. Furthermore, if v ∉ T, then p(v) ∈ T and v = p(p(v)) ∈ p(T), so T ∪ p(T) is the entire vertex set Fin n. Since p is injective, |p(T)| = |T|. Because T and p(T) are disjoint, |T| + |p(T)| = 2 * |T| = n.

    lines 19–33

    uses Finset.disjoint_left, Finset.mem_image.mp, Finset.mem_union, Finset.mem_image, Finset.mem_univ, iff_true, Or.inl, Finset.card_union_of_disjoint, Finset.card_univ, Fintype.card_fin, Finset.card_image_of_injective

      have hcard : 2 * T.card = n := by
        have hdisj : Disjoint T (T.image p) := by
          rw [Finset.disjoint_left]
          intro a ha hb
          obtain ⟨b, hbT, rfl⟩ := Finset.mem_image.mp hb
          exact ((hxor b).mp hbT) ha
        have hunion : T ∪ T.image p = Finset.univ := by
          ext v
          simp only [Finset.mem_union, Finset.mem_image, Finset.mem_univ, iff_true]
          by_cases hv : v ∈ T
          · exact Or.inl hv
          · right; exact ⟨p v, (hxor (p v)).mpr (by rw [hpp]; exact hv), hpp v⟩
        have := Finset.card_union_of_disjoint hdisj
        rw [hunion, Finset.card_univ, Fintype.card_fin, Finset.card_image_of_injective _ hpinj] at this
        omega
  4. We construct a permutation π of Fin n pairing each element of T at an even index with its partner at the following odd index.

    Let m = |T|, so n = 2m, and let e : Fin m → Fin n enumerate the elements of T. Define f : Fin n → Fin n by sending even indices 2j to e(j) and odd indices 2j + 1 to p(e(j)). By case analysis on parities and using that T and p(T) are disjoint while e and p are injective, f is injective. Since Fin n is finite, f is bijective and yields a permutation π.

    lines 34–49

    uses Subtype.ext, congrArg, Fin.val, Equiv.ofBijective, Finite.injective_iff_bijective.mp

      set m := T.card with hm
      let e : Fin m → Fin n := fun i => (T.equivFin.symm i : Fin n)
      have he_mem : ∀ i, e i ∈ T := fun i => (T.equivFin.symm i).2
      have he_inj : Function.Injective e := fun a b h =>
        T.equivFin.symm.injective (Subtype.ext h)
      let f : Fin n → Fin n := fun i =>
        if i.val % 2 = 0 then e ⟨i.val / 2, by omega⟩ else p (e ⟨i.val / 2, by omega⟩)
      have hf_inj : Function.Injective f := by
        intro a b hab
        simp only [f] at hab
        split_ifs at hab with ha hb hb
        · have := congrArg Fin.val (he_inj hab); simp at this; ext; omega
        · exact absurd (hab ▸ he_mem _) ((hxor _).mp (he_mem _))
        · exact absurd (hab.symm ▸ he_mem _) ((hxor _).mp (he_mem _))
        · have := congrArg Fin.val (he_inj (hpinj hab)); simp at this; ext; omega
      let π : Equiv.Perm (Fin n) := Equiv.ofBijective f (Finite.injective_iff_bijective.mp hf_inj)
  5. The permutation π aligns each consecutive pair (π(2j), π(2j+1)) with a matching edge directed in D.

    For each j with 2j + 1 < n, evaluating f gives π(2j) = e(j) and π(2j + 1) = p(e(j)). The pair (e(j), p(e(j))) is an edge of M by construction of p. Moreover, since e(j) ∈ T, the definition of T guarantees that D contains the directed edge e(j) → p(e(j)). Hence π witnesses the existential condition in the definition of the matching sign.

    lines 50–67

    uses if_pos, if_neg

      have hπ : ∃ π : Equiv.Perm (Fin n), ∀ (j : ℕ) (hj : 2 * j + 1 < n),
          M.Adj (π ⟨2 * j, by omega⟩) (π ⟨2 * j + 1, hj⟩) ∧
            D.Adj (π ⟨2 * j, by omega⟩) (π ⟨2 * j + 1, hj⟩) := by
        refine ⟨π, fun j hj => ?_⟩
        have h0 : π ⟨2 * j, by omega⟩ = e ⟨j, by omega⟩ := by
          show f ⟨2 * j, by omega⟩ = _
          simp only [f]
          rw [if_pos (by simp)]
          congr 1; ext; simp
        have h1 : π ⟨2 * j + 1, hj⟩ = p (e ⟨j, by omega⟩) := by
          show f ⟨2 * j + 1, hj⟩ = _
          simp only [f]
          rw [if_neg (by omega)]
          congr 2; ext; simp only; omega
        rw [h0, h1]
        refine ⟨hp _, ?_⟩
        have := he_mem ⟨j, by omega⟩
        simpa [hT] using this
  6. The value of orientation_perfect_matching_sign D M is either 1 or -1.

    Unfolding orientation_perfect_matching_sign, the witness π validates the existential condition, triggering the positive branch of the definition and reducing the value to the sign of the permutation. Since the sign of a permutation is an integer unit, and the only units in ℤ are 1 and -1, the sign is either 1 or -1.

    lines 68–70

    uses dif_pos, Int.units_eq_one_or

      unfold orientation_perfect_matching_sign
      rw [dif_pos hπ]
      rcases Int.units_eq_one_or (Equiv.Perm.sign hπ.choose) with h | h <;> rw [h] <;> simp
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
true_and
Conjunction with True simplifies to the proposition itself.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_image.mp
If an element belongs to the image of a set under a function, it is the image of some element in that set.
Finset.mem_union
An element belongs to the union of two finite sets if and only if it belongs to either set.
Finset.mem_image
An element is in the image of a set under a function if and only if it is the image of some element in the set.
iff_true
An equivalence between a proposition and True simplifies to the proposition itself.
Or.inl
A proof of the left disjunct proves a disjunction.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_univ
The cardinality of the universal finset is the cardinality of the underlying finite type.
Fintype.card_fin
The type Fin n has cardinality n.
Finset.card_image_of_injective
An injective map preserves the cardinality of a finite set under image.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
congrArg
Applying a function to equal arguments yields equal results.
Fin.val
The natural number value of an element of Fin n.
Equiv.ofBijective
A bijective map between two types yields an equivalence between them.
Finite.injective_iff_bijective.mp
An injective map from a finite type to itself is bijective.
if_pos
If the condition holds, an if-then-else expression evaluates to the then-branch.
if_neg
If the condition fails, an if-then-else expression evaluates to the else-branch.
dif_pos
A dependent if-then-else evaluates to its first branch when given a proof of the condition.
Int.units_eq_one_or
Every unit of the integers is either 1 or -1.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem orientation_perfect_matching_sign_eq_one_or_neg_one {n : ℕ} (G : SimpleGraph (Fin n))    (D : Digraph (Fin n)) (hD : is_graph_orientation G D) (M : G.Subgraph)    (hM : M.IsPerfectMatching) :    orientation_perfect_matching_sign D M = 1 ∨ orientation_perfect_matching_sign D M = -1 := by  classical  -- the partner map  have hex : ∀ v, ∃! w, M.Adj v w := fun v => hM.1 (hM.2 v)  choose p hp huniq using hex  have hpp : ∀ v, p (p v) = v := fun v => (huniq (p v) v (hp v).symm).symm  have hpinj : Function.Injective p := fun a b h => by rw [← hpp a, h, hpp b]  set T : Finset (Fin n) := Finset.univ.filter (fun v => D.Adj v (p v)) with hT  have hxor : ∀ v, v ∈ T ↔ p v ∉ T := by    intro v    have hG : G.Adj v (p v) := M.adj_sub (hp v)    have h1 := (hD.1 v (p v)).mpr hG    have h2 := hD.2 v (p v)    simp only [hT, Finset.mem_filter, Finset.mem_univ, true_and, hpp]    tauto  have hcard : 2 * T.card = n := by    have hdisj : Disjoint T (T.image p) := by      rw [Finset.disjoint_left]      intro a ha hb      obtain ⟨b, hbT, rfl⟩ := Finset.mem_image.mp hb      exact ((hxor b).mp hbT) ha    have hunion : T ∪ T.image p = Finset.univ := by      ext v      simp only [Finset.mem_union, Finset.mem_image, Finset.mem_univ, iff_true]      by_cases hv : v ∈ T      · exact Or.inl hv      · right; exact ⟨p v, (hxor (p v)).mpr (by rw [hpp]; exact hv), hpp v⟩    have := Finset.card_union_of_disjoint hdisj    rw [hunion, Finset.card_univ, Fintype.card_fin, Finset.card_image_of_injective _ hpinj] at this    omega  set m := T.card with hm  let e : Fin m → Fin n := fun i => (T.equivFin.symm i : Fin n)  have he_mem : ∀ i, e i ∈ T := fun i => (T.equivFin.symm i).2  have he_inj : Function.Injective e := fun a b h =>    T.equivFin.symm.injective (Subtype.ext h)  let f : Fin n → Fin n := fun i =>    if i.val % 2 = 0 then e ⟨i.val / 2, by omega⟩ else p (e ⟨i.val / 2, by omega⟩)  have hf_inj : Function.Injective f := by    intro a b hab    simp only [f] at hab    split_ifs at hab with ha hb hb    · have := congrArg Fin.val (he_inj hab); simp at this; ext; omega    · exact absurd (hab ▸ he_mem _) ((hxor _).mp (he_mem _))    · exact absurd (hab.symm ▸ he_mem _) ((hxor _).mp (he_mem _))    · have := congrArg Fin.val (he_inj (hpinj hab)); simp at this; ext; omega  let π : Equiv.Perm (Fin n) := Equiv.ofBijective f (Finite.injective_iff_bijective.mp hf_inj)  have hπ : ∃ π : Equiv.Perm (Fin n), ∀ (j : ℕ) (hj : 2 * j + 1 < n),      M.Adj (π ⟨2 * j, by omega⟩) (π ⟨2 * j + 1, hj⟩) ∧        D.Adj (π ⟨2 * j, by omega⟩) (π ⟨2 * j + 1, hj⟩) := by    refine ⟨π, fun j hj => ?_⟩    have h0 : π ⟨2 * j, by omega⟩ = e ⟨j, by omega⟩ := by      show f ⟨2 * j, by omega⟩ = _      simp only [f]      rw [if_pos (by simp)]      congr 1; ext; simp    have h1 : π ⟨2 * j + 1, hj⟩ = p (e ⟨j, by omega⟩) := by      show f ⟨2 * j + 1, hj⟩ = _      simp only [f]      rw [if_neg (by omega)]      congr 2; ext; simp only; omega    rw [h0, h1]    refine ⟨hp _, ?_⟩    have := he_mem ⟨j, by omega⟩    simpa [hT] using this  unfold orientation_perfect_matching_sign  rw [dif_pos hπ]  rcases Int.units_eq_one_or (Equiv.Perm.sign hπ.choose) with h | h <;> rw [h] <;> simp
See it in the graphDiscuss this resultChallenge it