finset_rank_two_cover_matching_bound
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
- simple_graph_common_neighbors_matching_of_avoided_packingFor a triangle-maximal family of size p avoiding an edge with d common neighbors, their induced graph contains a matching of size at least…
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.
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`.
uses
Finset.induction_onclassical revert hB induction B using Finset.induction_on with
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.
| empty => intro hB refine ⟨∅, by simp, by simp, by simp, ?_⟩ simpIn 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|$.
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'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$.
uses
Finset.mem_biUnion.mp,Finset.mem_biUnion.mprlet 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⟩
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.
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.mprby_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
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)$.
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
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$.
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
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|$.
uses
Finset.mem_insert_of_mem,Finset.biUnion_insert,Finset.card_insert_of_notMem,Finset.card_sdiff_add_cardrefine ⟨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|$.
- Linear arithmetic inequalities (such as combining cardinality bounds and deducing $|b| = 2$ from $|b| \le 2$ and $\neg(|b| \le 1)$) are closed by the `omega` decision procedure.
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.
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