finite_sym2_cross_outside_endpoints_card_le
For a finite set of unordered pairs, the union of outside endpoints of pairs incident with S has cardinality at most the number of pairs.
Statement
theorem finite_sym2_cross_outside_endpoints_card_le {V : Type*} [DecidableEq V] (S : Finset V) (D : Finset (Sym2 V)) : ((D.filter (fun e => ∃ a ∈ S, a ∈ e.toFinset)).biUnion (fun e => e.toFinset \ S)).card ≤ D.card
- Source
- Counting forbidden vertices in simple_graph_triangle_packing_pair_deletion_forcing_quadratic_kernel; state/campaigns/triangle_reductions/quadratic_kernel_in687.md.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
To bound the number of outside endpoints of pairs in D meeting S, let D' ⊆ D be the subcollection of pairs incident with S. Since every pair in D' contains at least one vertex in S and an unordered pair has at most two vertices in total, each pair contributes at most one endpoint outside S. The union bound then shows that the union of these outside endpoints has cardinality at most |D'| * 1 ≤ |D|.
Restrict attention to the subset D' ⊆ D of pairs incident with S.
We define D' as the subset of pairs e ∈ D that intersect S (having an endpoint in S). Outside endpoints of pairs in D can only arise from pairs incident with S, so it suffices to show that the union of outside endpoints e \\ S over all e ∈ D' has cardinality at most |D|.
classical let D' := D.filter (fun e => ∃ a ∈ S, a ∈ e.toFinset) change (D'.biUnion fun e => e.toFinset \ S).card ≤ D.card
Each pair e ∈ D' has at most one endpoint outside S, i.e., |e \\ S| ≤ 1.
Let e ∈ D'. By definition of D', there is a vertex a ∈ S with a ∈ e (via Finset.mem_filter.mp). Any outside vertex v ∈ e \\ S belongs to e and not S (via Finset.mem_sdiff.mp), so v ≠ a since a ∈ S. Thus v belongs to e \\ {a} (via Finset.mem_erase.mpr), which proves the inclusion e \\ S ⊆ e \\ {a}. Monotonicity of cardinality (Finset.card_le_card) and the formula for erasing a member (Finset.card_erase_of_mem) then give |e \\ S| ≤ |e| - 1. Moreover, by Sym2.card_toFinset, an unordered pair has 1 vertex if it is a self-loop and 2 vertices otherwise, so |e| ≤ 2 in all cases. Since a ∈ e, e is nonempty and |e| > 0 (Finset.card_pos.mpr). Combining |e \\ S| ≤ |e| - 1 with 1 ≤ |e| ≤ 2 via linear arithmetic (omega) yields |e \\ S| ≤ 1.
uses
Finset.mem_filter.mp,Finset.mem_sdiff.mp,Finset.mem_erase.mpr,Finset.card_le_card,Finset.card_erase_of_mem,Sym2.card_toFinset,Finset.card_pos.mprhave hone : ∀ e ∈ D', (e.toFinset \ S).card ≤ 1 := by intro e he obtain ⟨a,haS,hae⟩ := (Finset.mem_filter.mp he).2 have hs : e.toFinset \ S ⊆ e.toFinset.erase a := by intro v hv obtain ⟨hve,hvS⟩ := Finset.mem_sdiff.mp hv exact Finset.mem_erase.mpr ⟨by intro h; subst v; exact hvS haS,hve⟩ have hc := Finset.card_le_card hs rw [Finset.card_erase_of_mem hae] at hc have hec : e.toFinset.card ≤ 2 := by rw [Sym2.card_toFinset] split_ifs <;> omega have hp : 0 < e.toFinset.card := Finset.card_pos.mpr ⟨a,hae⟩ omega
The union of outside endpoints over all incident pairs has cardinality at most |D|.
Since each member set e \\ S has size at most 1, the union bound (Finset.card_biUnion_le_card_mul) implies that the cardinality of the union over D' is at most |D'| * 1. Because D' is obtained by filtering D, we have D' ⊆ D (Finset.filter_subset), which implies |D'| ≤ |D| (Finset.card_le_card). Simplifying |D'| * 1 = |D'| with Nat.mul_one, linear arithmetic (omega) concludes that the cardinality of the union is at most |D|.
uses
Finset.card_biUnion_le_card_mul,Finset.card_le_card,Finset.filter_subset,Nat.mul_onehave hB : (D'.biUnion fun e => e.toFinset \ S).card ≤ D'.card * 1 := Finset.card_biUnion_le_card_mul D' (fun e => e.toFinset \ S) 1 hone have hD : D'.card ≤ D.card := Finset.card_le_card (Finset.filter_subset _ _) simp only [Nat.mul_one] at hB omega
Finset.mem_filter.mp- If an element belongs to a filtered set {x ∈ s | p x}, then it belongs to s and satisfies p.
Finset.mem_sdiff.mp- If an element belongs to the difference s \\ t, then it belongs to s and does not belong to t.
Finset.mem_erase.mpr- An element v belongs to s with a removed if v ≠ a and v ∈ s.
Finset.card_le_card- If s ⊆ t, then the cardinality of s is at most that of t.
Finset.card_erase_of_mem- Removing an element a from a finite set s containing it decreases the cardinality by 1.
Sym2.card_toFinset- The set of vertices of an unordered pair z has cardinality 1 if z is a loop (diagonal) and 2 otherwise.
Finset.card_pos.mpr- A finite set containing at least one element has strictly positive cardinality.
Finset.card_biUnion_le_card_mul- The union of a collection of sets indexed by s, each having cardinality at most n, has cardinality at most |s| * n.
Finset.filter_subset- Filtering a finite set s by a predicate yields a subset of s.
Nat.mul_one- Multiplying any natural number by 1 gives the number itself.
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.
theorem finite_sym2_cross_outside_endpoints_card_le {V : Type*} [DecidableEq V] (S : Finset V) (D : Finset (Sym2 V)) : ((D.filter (fun e => ∃ a ∈ S, a ∈ e.toFinset)).biUnion (fun e => e.toFinset \ S)).card ≤ D.card := by classical let D' := D.filter (fun e => ∃ a ∈ S, a ∈ e.toFinset) change (D'.biUnion fun e => e.toFinset \ S).card ≤ D.card have hone : ∀ e ∈ D', (e.toFinset \ S).card ≤ 1 := by intro e he obtain ⟨a,haS,hae⟩ := (Finset.mem_filter.mp he).2 have hs : e.toFinset \ S ⊆ e.toFinset.erase a := by intro v hv obtain ⟨hve,hvS⟩ := Finset.mem_sdiff.mp hv exact Finset.mem_erase.mpr ⟨by intro h; subst v; exact hvS haS,hve⟩ have hc := Finset.card_le_card hs rw [Finset.card_erase_of_mem hae] at hc have hec : e.toFinset.card ≤ 2 := by rw [Sym2.card_toFinset] split_ifs <;> omega have hp : 0 < e.toFinset.card := Finset.card_pos.mpr ⟨a,hae⟩ omega have hB : (D'.biUnion fun e => e.toFinset \ S).card ≤ D'.card * 1 := Finset.card_biUnion_le_card_mul D' (fun e => e.toFinset \ S) 1 hone have hD : D'.card ≤ D.card := Finset.card_le_card (Finset.filter_subset _ _) simp only [Nat.mul_one] at hB omega