AFTD Auto-Formalizing Theoretical Domains

finset_rank_two_cover_matching_bound

theoremverified

For any finite family of sets of size at most two, some pairwise-disjoint subfamily of two-element sets has size at least the size of the union minus the number of sets.

Statement

theorem finset_rank_two_cover_matching_bound {α : Type*} [DecidableEq α]
    (B : Finset (Finset α)) (hB : ∀ b ∈ B, b.card ≤ 2) :
    ∃ M : Finset (Finset α), M ⊆ B ∧
      (M : Set (Finset α)).Pairwise Disjoint ∧
      (∀ e ∈ M, e.card = 2) ∧
      (B.biUnion id).card ≤ B.card + M.card
Source
Structural helper for the triangle packing-cover campaign, related to matching-cover reductions in https://arxiv.org/abs/2610.15269; see state/campaigns/triangle_reductions/high_codegree_route_in512.md.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The theorem is proved by induction on the finite set family $B$. The base case $B = \emptyset$ is trivial with $M = \emptyset$. In the inductive step with an added set $b$, we check whether $b$ is a 2-element set disjoint from the union of the inductive matching $M$. If so, adding $b$ to $M$ increases both $|B|$ and $|M|$ by 1 while the total union grows by at most $|b| = 2$, maintaining the bound. Otherwise, $b$ contributes at most one new element to $\bigcup B$ (either because $|b| \le 1$ or because it intersects $\bigcup M \subseteq \bigcup B$), so keeping the matching $M$ unchanged preserves the bound since $|B|$ increases by 1.

  1. It suffices to prove the theorem by induction on the finite set family $B$.

    We revert the assumption $hB$ that every member of $B$ has cardinality at most 2, and set up an induction on the finite set $B$ using `Finset.induction_on`.

    lines 11–13

    uses Finset.induction_on

      classical
      revert hB
      induction B using Finset.induction_on with
  2. The base case $B = \emptyset$ holds by choosing $M = \emptyset$.

    When $B$ is empty, we choose $M = \emptyset$. The requirements that $M \subseteq \emptyset$, that $M$ is pairwise disjoint, and that every element of $M$ has cardinality 2 are vacuously true. The cardinality bound $|\bigcup \emptyset| \le |\emptyset| + |M|$ simplifies to $0 \le 0 + 0$, which holds immediately.

    lines 14–17

      | empty =>
          intro hB
          refine ⟨∅, by simp, by simp, by simp, ?_⟩
          simp
  3. In the inductive step $B' = B \cup \{b\}$ with $b \notin B$, the induction hypothesis yields a matching $M \subseteq B$ for $B$.

    Given a new set $b \notin B$ such that every set in $B \cup \{b\}$ has size at most 2, we note that $|b| \le 2$ and every set in $B$ has size at most 2. Applying the induction hypothesis to $B$ produces a pairwise-disjoint family $M \subseteq B$ of 2-element sets satisfying $|\bigcup B| \le |B| + |M|$.

    lines 18–24

    uses Finset.mem_insert_self, Finset.mem_insert_of_mem

      | @insert b B hb ih =>
          intro hB
          have hbsize : b.card ≤ 2 := hB b (Finset.mem_insert_self _ _)
          have hB' : ∀ e ∈ B, e.card ≤ 2 := by
            intro e he
            exact hB e (Finset.mem_insert_of_mem he)
          obtain ⟨M, hMB, hMdis, hMtwo, hbound⟩ := ih hB'
  4. Setting $U = \bigcup B$, the union of the matching $\bigcup M$ is contained in $U$.

    Let $U = \bigcup B$. Since each element $e \in M$ also belongs to $B$, any element $x \in \bigcup M$ is contained in some $e \in B$, and therefore $x \in U$.

    lines 25–30

    uses Finset.mem_biUnion.mp, Finset.mem_biUnion.mpr

          let U := B.biUnion id
          change U.card ≤ B.card + M.card at hbound
          have hMU : M.biUnion id ⊆ U := by
            intro x hx
            obtain ⟨e, heM, hxe⟩ := Finset.mem_biUnion.mp hx
            exact Finset.mem_biUnion.mpr ⟨e, hMB heM, hxe⟩
  5. If $|b| = 2$ and $b$ is disjoint from $\bigcup M$, the extended family $M \cup \{b\}$ is a pairwise-disjoint family of 2-element sets in $B \cup \{b\}$.

    We case-split on whether $|b| = 2$ and $b$ is disjoint from $\bigcup M$. In this branch, because $b \notin B$ and $M \subseteq B$, we have $b \notin M$. Then $M \cup \{b\} \subseteq B \cup \{b\}$. Disjointness of $b$ from $\bigcup M$ ensures $b$ is disjoint from every $e \in M$, so $M \cup \{b\}$ remains pairwise disjoint. Every element of $M \cup \{b\}$ has size 2, since $|b| = 2$ and every element of $M$ has size 2.

    lines 31–52

    uses Finset.mem_insert.mp, Finset.mem_insert_self, Finset.mem_insert_of_mem, Finset.coe_insert, Finset.disjoint_left.mpr, Finset.disjoint_left.mp, Finset.mem_biUnion.mpr

          by_cases hgood : b.card = 2 ∧ Disjoint b (M.biUnion id)
          · have hbM : b ∉ M := by
              intro h
              exact hb (hMB h)
            refine ⟨insert b M, ?_, ?_, ?_, ?_⟩
            · intro e he
              rcases Finset.mem_insert.mp he with rfl | he
              · exact Finset.mem_insert_self _ _
              · exact Finset.mem_insert_of_mem (hMB he)
            · rw [Finset.coe_insert]
              refine hMdis.insert ?_
              intro e he _
              have hde : Disjoint b e := by
                apply Finset.disjoint_left.mpr
                intro x hxb hxe
                exact (Finset.disjoint_left.mp hgood.2) hxb
                  (Finset.mem_biUnion.mpr ⟨e, he, hxe⟩)
              exact ⟨hde, hde.symm⟩
            · intro e he
              rcases Finset.mem_insert.mp he with rfl | he
              · exact hgood.1
              · exact hMtwo e he
  6. The extended matching $M \cup \{b\}$ satisfies the cardinality bound $|\bigcup (B \cup \{b\})| \le |B \cup \{b\}| + |M \cup \{b\}|$.

    The union over $B \cup \{b\}$ is $b \cup U$. Since $b \notin B$ and $b \notin M$, the sizes are $|B \cup \{b\}| = |B| + 1$ and $|M \cup \{b\}| = |M| + 1$. By subadditivity, $|b \cup U| \le |b| + |U| \le 2 + |U|$. Together with the inductive bound $|U| \le |B| + |M|$, linear arithmetic (`omega`) confirms $|b \cup U| \le (|B| + 1) + (|M| + 1)$.

    lines 53–57

    uses Finset.biUnion_insert, Finset.card_insert_of_notMem, Finset.card_union_le

            · rw [Finset.biUnion_insert, Finset.card_insert_of_notMem hb,
                  Finset.card_insert_of_notMem hbM]
              have hu := Finset.card_union_le b U
              change (b ∪ U).card ≤ _
              omega
  7. If $|b| \ne 2$ or $b$ is not disjoint from $\bigcup M$, then $|b \setminus U| \le 1$.

    If $|b| \le 1$, then $|b \setminus U| \le |b| \le 1$ trivially. Otherwise $|b| > 1$, and since $|b| \le 2$, we must have $|b| = 2$. In that case, $b$ cannot be disjoint from $\bigcup M$, so there is some element $x \in b \cap \bigcup M \subseteq b \cap U$. Hence $|b \cap U| \ge 1$. Using the identity $|b \setminus U| + |b \cap U| = |b| = 2$, linear arithmetic gives $|b \setminus U| \le 1$.

    lines 58–69

    uses Finset.card_le_card, Finset.sdiff_subset, Finset.not_disjoint_iff.mp, Finset.one_le_card.mpr, Finset.mem_inter.mpr, Finset.card_sdiff_add_card_inter

          · have hdiff : (b \ U).card ≤ 1 := by
              by_cases hsmall : b.card ≤ 1
              · exact (Finset.card_le_card (Finset.sdiff_subset)).trans hsmall
              · have hb2 : b.card = 2 := by omega
                have hnotdis : ¬Disjoint b (M.biUnion id) := by
                  intro hd
                  exact hgood ⟨hb2, hd⟩
                obtain ⟨x, hxb, hxM⟩ := Finset.not_disjoint_iff.mp hnotdis
                have hinter : 1 ≤ (b ∩ U).card := Finset.one_le_card.mpr
                  ⟨x, Finset.mem_inter.mpr ⟨hxb, hMU hxM⟩⟩
                have hsum := Finset.card_sdiff_add_card_inter b U
                omega
  8. Keeping the existing matching $M$ unchanged satisfies all conditions for $B \cup \{b\}$.

    Since $M \subseteq B \subseteq B \cup \{b\}$, $M$ remains a pairwise-disjoint family of 2-element sets. The new union is $b \cup U$, whose cardinality is $|b \setminus U| + |U|$. Combining $|b \setminus U| \le 1$ with the induction hypothesis $|U| \le |B| + |M|$, linear arithmetic verifies that $|b \cup U| \le 1 + |B| + |M| = |B \cup \{b\}| + |M|$.

    lines 70–76

    uses Finset.mem_insert_of_mem, Finset.biUnion_insert, Finset.card_insert_of_notMem, Finset.card_sdiff_add_card

            refine ⟨M, ?_, hMdis, hMtwo, ?_⟩
            · intro e he
              exact Finset.mem_insert_of_mem (hMB he)
            · rw [Finset.biUnion_insert, Finset.card_insert_of_notMem hb]
              have hu := Finset.card_sdiff_add_card b U
              change (b ∪ U).card ≤ _
              omega
Finset.induction_on
Induction principle for finite sets: to prove a property for all finite sets, it suffices to prove it for the empty set and show that inserting a fresh element preserves the property.
Finset.mem_insert_self
An element $a$ belongs to the set $\{a\} \cup s$.
Finset.mem_insert_of_mem
If $a \in s$, then $a \in \{b\} \cup s$ for any $b$.
Finset.mem_biUnion.mp
An element belongs to a family union $\bigcup_{i \in I} s_i$ only if it belongs to some member set $s_i$.
Finset.mem_biUnion.mpr
If an element belongs to some set $s_i$ with $i \in I$, it belongs to the family union $\bigcup_{i \in I} s_i$.
Finset.mem_insert.mp
An element in $\{a\} \cup s$ is either equal to $a$ or an element of $s$.
Finset.coe_insert
Coercing the finite set $\{a\} \cup s$ to a set equals the set insertion of $a$ into the coercion of $s$.
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first belongs to the second.
Finset.disjoint_left.mp
If two finite sets are disjoint, any element of the first set is not in the second set.
Finset.biUnion_insert
The union of the sets in $\{a\} \cup s$ is the union of the set $t(a)$ and the union of the sets in $s$.
Finset.card_insert_of_notMem
Inserting a new element into a finite set increases its cardinality by 1.
Finset.card_union_le
The cardinality of the union of two finite sets is at most the sum of their cardinalities.
Finset.card_le_card
If $s \subseteq t$, then $|s| \le |t|$.
Finset.sdiff_subset
The set difference $s \setminus t$ is a subset of $s$.
Finset.not_disjoint_iff.mp
If two finite sets are not disjoint, they share at least one element.
Finset.one_le_card.mpr
A nonempty finite set has cardinality at least 1.
Finset.mem_inter.mpr
An element in both sets belongs to their intersection.
Finset.card_sdiff_add_card_inter
For finite sets $s$ and $t$, $|s \setminus t| + |s \cap t| = |s|$.
Finset.card_sdiff_add_card
For finite sets $s$ and $t$, $|s \setminus t| + |t| = |s \cup t|$.

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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem finset_rank_two_cover_matching_bound {α : Type*} [DecidableEq α]    (B : Finset (Finset α)) (hB : ∀ b ∈ B, b.card ≤ 2) :    ∃ M : Finset (Finset α), M ⊆ B ∧      (M : Set (Finset α)).Pairwise Disjoint ∧      (∀ e ∈ M, e.card = 2) ∧      (B.biUnion id).card ≤ B.card + M.card := by  classical  revert hB  induction B using Finset.induction_on with  | empty =>      intro hB      refine ⟨∅, by simp, by simp, by simp, ?_⟩      simp  | @insert b B hb ih =>      intro hB      have hbsize : b.card ≤ 2 := hB b (Finset.mem_insert_self _ _)      have hB' : ∀ e ∈ B, e.card ≤ 2 := by        intro e he        exact hB e (Finset.mem_insert_of_mem he)      obtain ⟨M, hMB, hMdis, hMtwo, hbound⟩ := ih hB'      let U := B.biUnion id      change U.card ≤ B.card + M.card at hbound      have hMU : M.biUnion id ⊆ U := by        intro x hx        obtain ⟨e, heM, hxe⟩ := Finset.mem_biUnion.mp hx        exact Finset.mem_biUnion.mpr ⟨e, hMB heM, hxe⟩      by_cases hgood : b.card = 2 ∧ Disjoint b (M.biUnion id)      · have hbM : b ∉ M := by          intro h          exact hb (hMB h)        refine ⟨insert b M, ?_, ?_, ?_, ?_⟩        · intro e he          rcases Finset.mem_insert.mp he with rfl | he          · exact Finset.mem_insert_self _ _          · exact Finset.mem_insert_of_mem (hMB he)        · rw [Finset.coe_insert]          refine hMdis.insert ?_          intro e he _          have hde : Disjoint b e := by            apply Finset.disjoint_left.mpr            intro x hxb hxe            exact (Finset.disjoint_left.mp hgood.2) hxb              (Finset.mem_biUnion.mpr ⟨e, he, hxe⟩)          exact ⟨hde, hde.symm⟩        · intro e he          rcases Finset.mem_insert.mp he with rfl | he          · exact hgood.1          · exact hMtwo e he        · rw [Finset.biUnion_insert, Finset.card_insert_of_notMem hb,              Finset.card_insert_of_notMem hbM]          have hu := Finset.card_union_le b U          change (b ∪ U).card ≤ _          omega      · have hdiff : (b \ U).card ≤ 1 := by          by_cases hsmall : b.card ≤ 1          · exact (Finset.card_le_card (Finset.sdiff_subset)).trans hsmall          · have hb2 : b.card = 2 := by omega            have hnotdis : ¬Disjoint b (M.biUnion id) := by              intro hd              exact hgood ⟨hb2, hd⟩            obtain ⟨x, hxb, hxM⟩ := Finset.not_disjoint_iff.mp hnotdis            have hinter : 1 ≤ (b ∩ U).card := Finset.one_le_card.mpr              ⟨x, Finset.mem_inter.mpr ⟨hxb, hMU hxM⟩⟩            have hsum := Finset.card_sdiff_add_card_inter b U            omega        refine ⟨M, ?_, hMdis, hMtwo, ?_⟩        · intro e he          exact Finset.mem_insert_of_mem (hMB he)        · rw [Finset.biUnion_insert, Finset.card_insert_of_notMem hb]          have hu := Finset.card_sdiff_add_card b U          change (b ∪ U).card ≤ _          omega
See it in the graphDiscuss this resultChallenge it