matroid_delete_singleton_loopless_and_coloopless_iff
Let M be a finite loopless and coloopless matroid on α and e ∈ M.E. Then the single-element deletion M.delete {e} is loopless; moreover, it is coloopless ((M.delete {e})✶.Loopless) if and only if e belongs to no two-element cocircuit of M (¬ ∃ C, M.IsCocircuit C ∧ e ∈ C ∧ C.ncard = 2).
Statement
theorem matroid_delete_singleton_loopless_and_coloopless_iff {α : Type*} (M : Matroid α) [M.Finite] [M.Loopless] [M✶.Loopless] (e : α) (he : e ∈ M.E) : (M.delete {e}).Loopless ∧ ((M.delete {e})✶.Loopless ↔ ¬ ∃ C, M.IsCocircuit C ∧ e ∈ C ∧ C.ncard = 2)
- Formalizes
- arXiv:2610.27706 Lemma 2.1(i)
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For any type α, any finite matroid M on α such that both M and its dual M✶ are loopless (i.e., M is loopless and coloopless), and any element e in the ground set M.E of M:
1. The deletion M.delete {e} is loopless; and
2. The dual of M.delete {e} is loopless (i.e., M.delete {e} has no coloops) if and only if there does not exist a cocircuit C of M such that e ∈ C and the cardinality of C (Set.ncard 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
Deleting an element e from a loopless matroid preserves looplessness because deletion is a restriction. By duality, the dual deletion (M \ {e})✶ is the contraction M✶ / {e}, whose loops are precisely the elements of M✶.closure({e}) \ {e}, so colooplessness of the deletion is equivalent to having no other element in the dual closure of {e}. This in turn holds if and only if {e} cannot be extended by an element f ≠ e to a circuit of M✶, meaning M has no 2-element cocircuit containing e.
The deletion M.delete {e} is loopless.
A deletion is a restriction of the original matroid. Since M is loopless by assumption, any restriction of M is also loopless.
uses
Matroid.delete_isRestrictionrefine ⟨(Matroid.delete_isRestriction M {e}).loopless, ?_⟩Colooplessness of M.delete {e} is equivalent to no element x ≠ e lying in the dual closure M✶.closure {e}.
By duality, (M.delete {e})✶ = M✶.contract {e}. A matroid is loopless if and only if its set of loops is empty, and the loops of M✶.contract {e} are precisely the elements in M✶.closure {e} \ {e}. Hence (M.delete {e})✶ is loopless if and only if no element distinct from e belongs to M✶.closure {e}. In addition, e belongs to the dual ground set M✶.E because M✶.E = M.E.
uses
Matroid.dual_delete,Matroid.loopless_iff,Matroid.contract_loops_eq,Set.eq_empty_iff_forall_notMem,M.dual_groundrw [Matroid.dual_delete, Matroid.loopless_iff, Matroid.contract_loops_eq, Set.eq_empty_iff_forall_notMem] simp only [Set.mem_sdiff, Set.mem_singleton_iff] have he_dual : e ∈ M✶.E := by rw [M.dual_ground]; exact he
In the forward direction, if a 2-element cocircuit C contains e, then C = {e, f} for some f ≠ e.
We proceed by contradiction: assuming no x ≠ e belongs to M✶.closure {e}, suppose there exists a cocircuit C containing e with |C| = 2. A 2-element set can be written as {x, y} with x ≠ y. Since e ∈ C, either e = x or e = y, so C can be written as {e, f} with f ≠ e.
uses
Set.ncard_eq_two,Set.pair_commconstructor · intro h ⟨C, hC, heC, hCcard⟩ obtain ⟨f, hfe, rfl⟩ : ∃ f, f ≠ e ∧ C = {e, f} := by obtain ⟨x, y, hxy, rfl⟩ := Set.ncard_eq_two.mp hCcard simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at heC rcases heC with rfl | rfl · exact ⟨y, hxy.symm, rfl⟩ · exact ⟨x, hxy, by rw [Set.pair_comm]⟩
The existence of the cocircuit {e, f} implies f ∈ M✶.closure {e}, contradicting the assumption.
Since C = {e, f} is a cocircuit of M, it is a circuit of M✶. Removing any element from a circuit leaves a basis, so {e, f} \ {f} is a basis of {e, f} in M✶. Since f ≠ e, {e, f} \ {f} = {e}. Because any set is contained in the closure of its basis, {e, f} ⊆ M✶.closure {e}, which implies f ∈ M✶.closure {e}. This contradicts the assumption that no element other than e belongs to M✶.closure {e}.
uses
Set.mem_insert_of_mem,Or.inlhave hmem : f ∈ ({e, f} : Set α) := Set.mem_insert_of_mem e rfl have hbas := hC.sdiff_singleton_isBasis hmem have hdiff : ({e, f} : Set α) \ {f} = {e} := by ext x simp only [Set.mem_sdiff, Set.mem_insert_iff, Set.mem_singleton_iff] constructor · rintro ⟨rfl | rfl, hne⟩ · rfl · contradiction · rintro rfl exact ⟨Or.inl rfl, hfe.symm⟩ rw [hdiff] at hbas have hcl : f ∈ M✶.closure {e} := hbas.subset_closure (Set.mem_insert_of_mem e rfl) exact h f ⟨hcl, hfe⟩
In the backward direction, assuming for contradiction that some f ≠ e lies in M✶.closure {e}, the singleton {e} is independent in M✶ and f ∉ {e}.
Assuming M has no 2-element cocircuit containing e, suppose for contradiction that some f ≠ e satisfies f ∈ M✶.closure {e}. Since M is coloopless, the dual M✶ is loopless; as e ∈ M✶.E, e is a nonloop, so the singleton {e} is independent in M✶. Also, f ∉ {e} because f ≠ e.
uses
Matroid.isNonloop_of_loopless· intro h f ⟨hfcl, hfe⟩ apply h have hI : M✶.Indep {e} := (Matroid.isNonloop_of_loopless he_dual).indep have heI : f ∉ ({e} : Set α) := by simp [hfe]
The pair {e, f} forms a 2-element cocircuit containing e, which is a contradiction.
For the single element x ∈ {e}, we have {e} \ {x} = ∅. The closure of the empty set in M✶ is the set of loops, which is empty because M✶ is loopless. Hence f ∉ M✶.closure ({e} \ {x}). Because {e} is independent in M✶, f ∉ {e}, f ∈ M✶.closure {e}, and f is not in the closure of any proper subset of {e}, the circuit extension criterion ensures that {f, e} = {e, f} is a circuit of M✶ (a cocircuit of M). Since f ≠ e, it has size 2 and contains e, contradicting the assumption that no such cocircuit exists.
uses
Set.sdiff_self,Matroid.closure_empty,Matroid.loops_eq_empty,Set.notMem_empty,Set.pair_comm,Set.mem_insert,Set.ncard_eq_twohave h_min : ∀ x ∈ ({e} : Set α), f ∉ M✶.closure ({e} \ {x}) := by intro x hx simp only [Set.mem_singleton_iff] at hx subst hx rw [Set.sdiff_self, Matroid.closure_empty, Matroid.loops_eq_empty] exact Set.notMem_empty f have hcirc := hI.insert_isCircuit_of_forall heI hfcl h_min rw [Set.pair_comm] at hcirc refine ⟨{e, f}, hcirc, Set.mem_insert _ _, ?_⟩ rw [Set.ncard_eq_two] exact ⟨e, f, fun h => hfe h.symm, rfl⟩
Matroid.delete_isRestriction- Deleting a set of elements from a matroid produces a restriction of that matroid.
Matroid.dual_delete- The dual of a matroid deletion is the contraction by the same set in 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.contract_loops_eq- The loops of a contraction M / C are the elements in the closure of C outside C, i.e., M.closure(C) \ C.
Set.eq_empty_iff_forall_notMem- A set is empty if and only if it contains no elements.
M.dual_ground- The ground set of the dual matroid M✶ is equal to the ground set of M.
Set.ncard_eq_two- A set has cardinality 2 if and only if it is an unordered pair of two distinct elements.
Set.pair_comm- Unordered pairs are commutative: {a, b} = {b, a}.
Set.mem_insert_of_mem- If an element belongs to a set s, it also belongs to {y} ∪ s.
Or.inl- A disjunction a ∨ b holds if its left disjunct a holds.
Matroid.isNonloop_of_loopless- Every element of the ground set of a loopless matroid is a nonloop.
Set.sdiff_self- The difference of any set with itself is empty: s \ s = ∅.
Matroid.closure_empty- The closure of the empty set in a matroid is its set of loops.
Matroid.loops_eq_empty- In a loopless matroid, the set of loops is empty.
Set.notMem_empty- No element belongs to the empty set.
Set.mem_insert- An element x belongs to {x} ∪ s.
- In Lean's matroid library, cocircuits of a matroid M are represented as circuits of the dual matroid M✶, and colooplessness is represented by the typeclass `M✶.Loopless`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Deleting an element from a loopless and coloopless matroid produces a loopless matroid; moreover, it is coloopless if and only if the element belongs to no 2-element cocircuit. -/theorem matroid_delete_singleton_loopless_and_coloopless_iff {α : Type*} (M : Matroid α) [M.Finite] [M.Loopless] [M✶.Loopless] (e : α) (he : e ∈ M.E) : (M.delete {e}).Loopless ∧ ((M.delete {e})✶.Loopless ↔ ¬ ∃ C, M.IsCocircuit C ∧ e ∈ C ∧ C.ncard = 2) := by refine ⟨(Matroid.delete_isRestriction M {e}).loopless, ?_⟩ rw [Matroid.dual_delete, Matroid.loopless_iff, Matroid.contract_loops_eq, Set.eq_empty_iff_forall_notMem] simp only [Set.mem_sdiff, Set.mem_singleton_iff] have he_dual : e ∈ M✶.E := by rw [M.dual_ground]; exact he constructor · intro h ⟨C, hC, heC, hCcard⟩ obtain ⟨f, hfe, rfl⟩ : ∃ f, f ≠ e ∧ C = {e, f} := by obtain ⟨x, y, hxy, rfl⟩ := Set.ncard_eq_two.mp hCcard simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at heC rcases heC with rfl | rfl · exact ⟨y, hxy.symm, rfl⟩ · exact ⟨x, hxy, by rw [Set.pair_comm]⟩ have hmem : f ∈ ({e, f} : Set α) := Set.mem_insert_of_mem e rfl have hbas := hC.sdiff_singleton_isBasis hmem have hdiff : ({e, f} : Set α) \ {f} = {e} := by ext x simp only [Set.mem_sdiff, Set.mem_insert_iff, Set.mem_singleton_iff] constructor · rintro ⟨rfl | rfl, hne⟩ · rfl · contradiction · rintro rfl exact ⟨Or.inl rfl, hfe.symm⟩ rw [hdiff] at hbas have hcl : f ∈ M✶.closure {e} := hbas.subset_closure (Set.mem_insert_of_mem e rfl) exact h f ⟨hcl, hfe⟩ · intro h f ⟨hfcl, hfe⟩ apply h have hI : M✶.Indep {e} := (Matroid.isNonloop_of_loopless he_dual).indep have heI : f ∉ ({e} : Set α) := by simp [hfe] have h_min : ∀ x ∈ ({e} : Set α), f ∉ M✶.closure ({e} \ {x}) := by intro x hx simp only [Set.mem_singleton_iff] at hx subst hx rw [Set.sdiff_self, Matroid.closure_empty, Matroid.loops_eq_empty] exact Set.notMem_empty f have hcirc := hI.insert_isCircuit_of_forall heI hfcl h_min rw [Set.pair_comm] at hcirc refine ⟨{e, f}, hcirc, Set.mem_insert _ _, ?_⟩ rw [Set.ncard_eq_two] exact ⟨e, f, fun h => hfe h.symm, rfl⟩