AFTD Auto-Formalizing Theoretical Domains

finite_sym2_cross_outside_endpoints_card_le

theoremverified

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|.

  1. 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|.

    lines 5–7

      classical
      let D' := D.filter (fun e => ∃ a ∈ S, a ∈ e.toFinset)
      change (D'.biUnion fun e => e.toFinset \ S).card ≤ D.card
  2. 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.

    lines 8–21

    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.mpr

      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
  3. 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|.

    lines 22–26

    uses Finset.card_biUnion_le_card_mul, Finset.card_le_card, Finset.filter_subset, Nat.mul_one

      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
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

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
See it in the graphDiscuss this resultChallenge it