AFTD Auto-Formalizing Theoretical Domains

op_639_transversal_four_singleton_nonempty

theoremverified

For any minimal transversal T of size 4 in a hypergraph with covering number at least 4, and any element x in T, there exists an edge e in F such that e ∩ T = {x}.

Statement

theorem op_639_transversal_four_singleton_nonempty
    {V : Type*} [DecidableEq V] (F : Finset (Finset V))
    (htau_ge : ∀ T : Finset V, T.card < 4 → ∃ e ∈ F, Disjoint e T)
    (T : Finset V) (hT : T.card = 4) (hT_trans : ∀ e ∈ F, ¬Disjoint e T)
    (x : V) (hx : x ∈ T) :
    ∃ e ∈ F, e ∩ T = {x}
Source
step towards op_639_intersecting_four_uniform_covering_four_card_le_forty_two
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

Removing x from T leaves a subset of size 3. By the hypothesis that the hypergraph has covering number at least 4, this 3-element set cannot cover all edges, so there exists an edge e ∈ F disjoint from T \setminus {x}. Since T is a transversal, e must still intersect T, and because it avoids every element of T other than x, that intersection must be precisely {x}.

  1. |T \setminus {x}| < 4

    Since x ∈ T and |T| = 4, removing x leaves a set of cardinality 4 - 1 = 3, which is strictly less than 4.

    lines 8–10

    uses Finset.card_erase_of_mem

      have hcard : (T.erase x).card < 4 := by
        rw [Finset.card_erase_of_mem hx, hT]
        norm_num
  2. There exists an edge e ∈ F that is disjoint from T \setminus {x}

    Applying the assumption that the covering number is at least 4 (htau_ge) to the 3-element set T \setminus {x} yields an edge e ∈ F disjoint from it.

    line 11

      obtain ⟨e, heF, he_disj⟩ := htau_ge (T.erase x) hcard
  3. Every element in e ∩ T is equal to x

    Suppose for contradiction that some y ∈ e ∩ T is not equal to x. Then y ∈ T \setminus {x}, which contradicts the fact that e is disjoint from T \setminus {x}. Therefore, any y ∈ e ∩ T must be x.

    lines 12–17

    uses Finset.mem_inter, Finset.mem_erase.mpr, Finset.disjoint_left.mp

      have huniq : ∀ y, y ∈ e ∩ T → y = x := by
        intro y hy
        rw [Finset.mem_inter] at hy
        by_contra hne
        have hyerase : y ∈ T.erase x := Finset.mem_erase.mpr ⟨hne, hy.2⟩
        exact (Finset.disjoint_left.mp he_disj hy.1) hyerase
  4. The intersection e ∩ T is nonempty, and x ∈ e ∩ T

    Because T is a transversal, the edge e must intersect T, so e ∩ T is nonempty. Choosing any witness y ∈ e ∩ T, the uniqueness property from the previous step implies y = x, which shows that x ∈ e ∩ T.

    lines 18–22

    uses Finset.not_disjoint_iff_nonempty_inter.mp

      have hnonempty : (e ∩ T).Nonempty :=
        Finset.not_disjoint_iff_nonempty_inter.mp (hT_trans e heF)
      obtain ⟨y, hy⟩ := hnonempty
      have hxy : x ∈ e ∩ T := by
        simpa [huniq y hy] using hy
  5. The edge e satisfies e ∩ T = {x}

    Since x ∈ e ∩ T and every element in e ∩ T equals x, the intersection is exactly the singleton {x}.

    lines 23–24

    uses Finset.eq_singleton_iff_unique_mem.mpr

      refine ⟨e, heF, ?_⟩
      exact Finset.eq_singleton_iff_unique_mem.mpr ⟨hxy, huniq⟩
Finset.card_erase_of_mem
Removing an element belonging to a finite set decreases its cardinality by 1.
Finset.mem_inter
An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
Finset.mem_erase.mpr
An element belongs to the set obtained by erasing a if it is distinct from a and belongs to the original set.
Finset.disjoint_left.mp
If two sets are disjoint, any element of the first set cannot belong to the second set.
Finset.not_disjoint_iff_nonempty_inter.mp
If two sets are not disjoint, their intersection is nonempty.
Finset.eq_singleton_iff_unique_mem.mpr
A finite set equals the singleton {a} if a belongs to the set and every element in the set equals a.

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

/-- For any minimal transversal T of size 4 in a hypergraph with tau >= 4, and any x in T, there is an edge meeting T in {x}. -/theorem op_639_transversal_four_singleton_nonempty    {V : Type*} [DecidableEq V] (F : Finset (Finset V))    (htau_ge : ∀ T : Finset V, T.card < 4 → ∃ e ∈ F, Disjoint e T)    (T : Finset V) (hT : T.card = 4) (hT_trans : ∀ e ∈ F, ¬Disjoint e T)    (x : V) (hx : x ∈ T) :    ∃ e ∈ F, e ∩ T = {x} := by  have hcard : (T.erase x).card < 4 := by    rw [Finset.card_erase_of_mem hx, hT]    norm_num  obtain ⟨e, heF, he_disj⟩ := htau_ge (T.erase x) hcard  have huniq : ∀ y, y ∈ e ∩ T → y = x := by    intro y hy    rw [Finset.mem_inter] at hy    by_contra hne    have hyerase : y ∈ T.erase x := Finset.mem_erase.mpr ⟨hne, hy.2⟩    exact (Finset.disjoint_left.mp he_disj hy.1) hyerase  have hnonempty : (e ∩ T).Nonempty :=    Finset.not_disjoint_iff_nonempty_inter.mp (hT_trans e heF)  obtain ⟨y, hy⟩ := hnonempty  have hxy : x ∈ e ∩ T := by    simpa [huniq y hy] using hy  refine ⟨e, heF, ?_⟩  exact Finset.eq_singleton_iff_unique_mem.mpr ⟨hxy, huniq⟩
See it in the graphDiscuss this resultChallenge it