AFTD Auto-Formalizing Theoretical Domains

matroid_contract_singleton_coloopless_and_loopless_iff

theoremverifiedformalization

Let M be a finite loopless and coloopless matroid on α and e ∈ M.E. Then the single-element contraction M.contract {e} is coloopless (i.e. (M.contract {e})✶.Loopless), and (M.contract {e}) is loopless if and only if e belongs to no two-element circuit of M (¬ ∃ C, M.IsCircuit C ∧ e ∈ C ∧ C.ncard = 2).

Statement

theorem matroid_contract_singleton_coloopless_and_loopless_iff
    {α : Type*} (M : Matroid α) [M.Finite] [M.Loopless] [M✶.Loopless]
    (e : α) (he : e ∈ M.E) :
    (M.contract {e})✶.Loopless ∧
    ((M.contract {e}).Loopless ↔ ¬ ∃ C, M.IsCircuit C ∧ e ∈ C ∧ C.ncard = 2)
Formalizes
arXiv:2610.27706 Lemma 2.1(ii)
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

Let $α$ be a type, and let $M$ be a finite, loopless matroid on $α$ whose dual $M^*$ is also loopless (i.e., $M$ has no coloops). Let $e \in M.E$ be an element of the ground set of $M$. Then: 1. The dual of the contraction $(M / \{e\})^*$ is loopless (i.e., the contraction $M / \{e\}$ has no coloops), and 2. The contraction $M / \{e\}$ is loopless if and only if there does not exist a circuit $C$ of $M$ such that $e \in C$ and the cardinality of $C$ is 2.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof first establishes that contracting an element e from a coloopless matroid preserves colooplessness: by duality, (M / {e})✶ = M✶ \ {e}, and deleting an element from the dual loopless matroid M✶ produces no loops. Second, the contraction M / {e} is loopless if and only if its loop set cl({e}) \ {e} is empty, meaning every element in the closure of {e} equals e. If e belonged to a 2-element circuit {e, y}, then y would be in cl({e}), creating a loop in the contraction. Conversely, if some f ≠ e belongs to cl({e}), there is a circuit C ⊆ {f, e} containing f; since M is loopless, C cannot be a singleton loop {f}, forcing C = {f, e} to be a 2-element circuit containing e.

  1. The contracted matroid M / {e} is coloopless (its dual is loopless).

    We split the conjunction into its two goals. For the first conjunct, by matroid duality, contracting {e} in M is dual to deleting {e} from M✶. Since M is coloopless, M✶ has no loops. Deleting an element from a loopless matroid leaves no loops (the loops of M✶ \ {e} are M✶.loops \ {e} = ∅ \ {e} = ∅). Hence (M / {e})✶ is loopless.

    lines 7–8

    uses Matroid.dual_contract, Matroid.loopless_iff, Matroid.delete_loops_eq, Matroid.loops_eq_empty, Set.empty_sdiff

      refine ⟨?_, ?_⟩
      · rw [Matroid.dual_contract, Matroid.loopless_iff, Matroid.delete_loops_eq, Matroid.loops_eq_empty, Set.empty_sdiff]
  2. The contraction M / {e} is loopless if and only if cl({e}) = {e} (every element in cl({e}) equals e).

    By definition, M / {e} is loopless if and only if its loop set is empty. The loops of M / {e} are given by cl({e}) \ {e}. This difference is empty precisely when no element belongs to it, which simplifies logically to: every element x ∈ cl({e}) must satisfy x = e. We split this bi-implication into its two directions.

    lines 9–11

    uses Matroid.loopless_iff, Matroid.contract_loops_eq, Set.eq_empty_iff_forall_notMem, Set.mem_sdiff, Set.mem_singleton_iff, not_and, not_not

      · rw [Matroid.loopless_iff, Matroid.contract_loops_eq, Set.eq_empty_iff_forall_notMem]
        simp only [Set.mem_sdiff, Set.mem_singleton_iff, not_and, not_not]
        constructor
  3. If cl({e}) = {e}, then e belongs to no two-element circuit of M.

    Assume every element in cl({e}) equals e. Suppose for contradiction that there exists a circuit C containing e with |C| = 2. Writing C = {x, y} with x ≠ y, the condition e ∈ C implies either e = x or e = y. If e = x, then C = {e, y} with e ≠ y; since C is a circuit containing y, removing y places y in the closure of the remainder, so y ∈ cl({e}), which forces y = e, a contradiction. Symmetrically, if e = y, then x ∈ cl({e}) forces x = e, contradicting x ≠ e.

    lines 12–25

    uses Set.ncard_eq_two.1, Set.mem_insert_iff, Set.mem_singleton_iff, Ne.symm

        · intro h ⟨C, hC, heC, hcard⟩
          obtain ⟨x, y, hxy, rfl⟩ := Set.ncard_eq_two.1 hcard
          simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at heC
          rcases heC with rfl | rfl
          · have hyC : y ∈ ({e, y} : Set α) := by simp
            have hcl := hC.mem_closure_sdiff_singleton_of_mem hyC
            have : ({e, y} : Set α) \ {y} = {e} := by simp [hxy]
            rw [this] at hcl
            exact hxy.symm (h y hcl)
          · have hxC : x ∈ ({x, e} : Set α) := by simp
            have hcl := hC.mem_closure_sdiff_singleton_of_mem hxC
            have : ({x, e} : Set α) \ {x} = {e} := by simp [Ne.symm hxy]
            rw [this] at hcl
            exact hxy (h x hcl)
  4. Assuming e belongs to no 2-element circuit, any element f ∈ cl({e}) distinct from e gives a circuit C ⊆ {f, e} containing f.

    For the converse implication, assume e belongs to no 2-element circuit, let f ∈ cl({e}), and suppose for contradiction that f ≠ e. Then f ∉ {e}. By the characterization of matroid closure via circuits, f ∈ cl({e}) implies there exists a circuit C ⊆ {f, e} such that f ∈ C.

    lines 26–30

    uses Matroid.mem_closure_iff_exists_isCircuit

        · intro h f hf
          by_contra hfe
          apply h
          have hf_not : f ∉ ({e} : Set α) := by simpa
          obtain ⟨C, hCsub, hC, hfC⟩ := (Matroid.mem_closure_iff_exists_isCircuit hf_not).1 hf
  5. The circuit C must contain e.

    We prove e ∈ C by contradiction: if e ∉ C, then since C ⊆ {f, e}, the only element C can contain is f, so C = {f}. But a singleton circuit is a loop of M, which contradicts the hypothesis that M is loopless. Hence e must belong to C.

    lines 31–47

    uses Set.mem_singleton_iff, Set.mem_insert_iff, Matroid.singleton_isCircuit.1

          have heC : e ∈ C := by
            by_contra heC
            have : C = {f} := by
              ext x
              simp only [Set.mem_singleton_iff]
              constructor
              · intro hxC
                have := hCsub hxC
                simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at this
                obtain rfl | rfl := this
                · rfl
                · exact (heC hxC).elim
              · rintro rfl
                exact hfC
            subst this
            have hloop := Matroid.singleton_isCircuit.1 hC
            exact M.not_isLoop f hloop
  6. The circuit C equals {f, e}, forming a 2-element circuit containing e, which contradicts the hypothesis.

    Since C ⊆ {f, e} and both f ∈ C and e ∈ C, we have C = {f, e}. Because f ≠ e, this pair has cardinality 2. Thus C is a 2-element circuit containing e, contradicting the assumption that no such circuit exists. This completes the contradiction, proving f = e and hence that M / {e} is loopless.

    lines 48–56

    uses Set.mem_insert_iff, Set.mem_singleton_iff, Set.ncard_pair

          have hCeq : C = {f, e} := by
            ext x
            simp only [Set.mem_insert_iff, Set.mem_singleton_iff]
            refine ⟨fun hx ↦ hCsub hx, fun hx ↦ ?_⟩
            obtain rfl | rfl := hx
            · exact hfC
            · exact heC
          refine ⟨C, hC, heC, ?_⟩
          rw [hCeq, Set.ncard_pair hfe]
Matroid.dual_contract
The dual of contracting a set X equals deleting X from the dual matroid: (M / X)✶ = M✶ \ X.
Matroid.loopless_iff
A matroid is loopless if and only if its set of loops is empty.
Matroid.delete_loops_eq
The loops of a deletion M \ D are the loops of M minus D: (M \ D).loops = M.loops \ D.
Matroid.loops_eq_empty
In any loopless matroid, the set of loops is empty.
Set.empty_sdiff
Removing any set from the empty set leaves the empty set: ∅ \ s = ∅.
Matroid.contract_loops_eq
The loops of a contraction M / C are the elements in the closure of C outside C: (M / C).loops = cl(C) \ C.
Set.eq_empty_iff_forall_notMem
A set is empty if and only if no element belongs to it.
Set.mem_sdiff
An element belongs to s \ t if and only if it belongs to s and not to t.
Set.mem_singleton_iff
An element belongs to a singleton {b} if and only if it equals b.
not_and
The negation ¬(a ∧ b) is equivalent to a → ¬b.
not_not
Double negation elimination: ¬¬a ↔ a.
Set.ncard_eq_two.1
If a set has cardinality 2, it is of the form {x, y} for two distinct elements x ≠ y.
Set.mem_insert_iff
An element belongs to insert a s if and only if it equals a or belongs to s.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Matroid.mem_closure_iff_exists_isCircuit
For an element e ∉ X, e belongs to cl(X) if and only if there exists a circuit C ⊆ X ∪ {e} containing e.
Matroid.singleton_isCircuit.1
If a singleton {x} is a circuit, then x is a loop.
Set.ncard_pair
If a ≠ b, the unordered pair {a, b} has cardinality 2.

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

/-- Contracting an element from a loopless and coloopless matroid produces a coloopless matroid, which is loopless if and only if the element belongs to no 2-element circuit. -/theorem matroid_contract_singleton_coloopless_and_loopless_iff    {α : Type*} (M : Matroid α) [M.Finite] [M.Loopless] [M✶.Loopless]    (e : α) (he : e ∈ M.E) :    (M.contract {e})✶.Loopless ∧    ((M.contract {e}).Loopless ↔ ¬ ∃ C, M.IsCircuit C ∧ e ∈ C ∧ C.ncard = 2) := by  refine ⟨?_, ?_⟩  · rw [Matroid.dual_contract, Matroid.loopless_iff, Matroid.delete_loops_eq, Matroid.loops_eq_empty, Set.empty_sdiff]  · rw [Matroid.loopless_iff, Matroid.contract_loops_eq, Set.eq_empty_iff_forall_notMem]    simp only [Set.mem_sdiff, Set.mem_singleton_iff, not_and, not_not]    constructor    · intro h ⟨C, hC, heC, hcard⟩      obtain ⟨x, y, hxy, rfl⟩ := Set.ncard_eq_two.1 hcard      simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at heC      rcases heC with rfl | rfl      · have hyC : y ∈ ({e, y} : Set α) := by simp        have hcl := hC.mem_closure_sdiff_singleton_of_mem hyC        have : ({e, y} : Set α) \ {y} = {e} := by simp [hxy]        rw [this] at hcl        exact hxy.symm (h y hcl)      · have hxC : x ∈ ({x, e} : Set α) := by simp        have hcl := hC.mem_closure_sdiff_singleton_of_mem hxC        have : ({x, e} : Set α) \ {x} = {e} := by simp [Ne.symm hxy]        rw [this] at hcl        exact hxy (h x hcl)    · intro h f hf      by_contra hfe      apply h      have hf_not : f ∉ ({e} : Set α) := by simpa      obtain ⟨C, hCsub, hC, hfC⟩ := (Matroid.mem_closure_iff_exists_isCircuit hf_not).1 hf      have heC : e ∈ C := by        by_contra heC        have : C = {f} := by          ext x          simp only [Set.mem_singleton_iff]          constructor          · intro hxC            have := hCsub hxC            simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at this            obtain rfl | rfl := this            · rfl            · exact (heC hxC).elim          · rintro rfl            exact hfC        subst this        have hloop := Matroid.singleton_isCircuit.1 hC        exact M.not_isLoop f hloop      have hCeq : C = {f, e} := by        ext x        simp only [Set.mem_insert_iff, Set.mem_singleton_iff]        refine ⟨fun hx ↦ hCsub hx, fun hx ↦ ?_⟩        obtain rfl | rfl := hx        · exact hfC        · exact heC      refine ⟨C, hC, heC, ?_⟩      rw [hCeq, Set.ncard_pair hfe]
See it in the graphDiscuss this resultChallenge it