AFTD Auto-Formalizing Theoretical Domains

simple_graph_sum_choose_degree_two_le_choose_card_edgeFinset

theoremverified

In any finite simple graph, the number of pairs of edges sharing a vertex, ∑_v C(d(v),2), is at most C(|E|,2): two distinct edges share at most one vertex.

Statement

theorem simple_graph_sum_choose_degree_two_le_choose_card_edgeFinset {V : Type*} [Fintype V]
    [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] :
    ∑ v, (G.degree v).choose 2 ≤ G.edgeFinset.card.choose 2
Source
Helper for arXiv:2610.12109 (Sharp linear Turán remainders for cycle and edge extremality), Lemma 2.5 (upper bound σ₂(T) ≤ C(k−1,2)); holds for every simple graph.
Verified
12 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 2

The proof, explained

The inequality is proved by constructing an injection from pairs of incident edges to pairs of edges of the graph. The sum ∑_v C(d(v), 2) is expressed as the cardinality of the set of pairs (v, s), where v is a vertex and s is a 2-element set of edges incident to v. The projection map (v, s) ↦ s sends each incident pair to a 2-element subset of the graph's edge set, which has cardinality C(|E|, 2). This map is injective because in a simple graph, two distinct vertices can share at most one common incident edge, so no two distinct edges can be incident to two different vertices.

  1. The inequality reduces to showing that the projection map (v, s) ↦ s from the disjoint union ∑_{v} C(E(v), 2) into C(E, 2) is well-defined and injective.

    For each vertex v, C(d(v), 2) is rewritten as the cardinality of the 2-element subsets of the incidence set E(v) using Finset.card_powersetCard and SimpleGraph.card_incidenceFinset_eq_degree. Summing these over all vertices gives the cardinality of the disjoint union (sigma Finset) via Finset.card_sigma. Likewise, C(|E|, 2) is rewritten as the cardinality of the 2-element subsets of the edge set E. Applying Finset.card_le_card_of_injOn reduces the inequality to showing that the projection (v, s) ↦ s maps into 2-element edge sets and is injective.

    lines 4–10

    uses Finset.card_powersetCard, SimpleGraph.card_incidenceFinset_eq_degree, Finset.card_sigma, Finset.card_le_card_of_injOn

      classical
      have hdeg : ∀ v, (G.degree v).choose 2 = ((G.incidenceFinset v).powersetCard 2).card := by
        intro v
        rw [Finset.card_powersetCard, SimpleGraph.card_incidenceFinset_eq_degree]
      simp_rw [hdeg]
      rw [← Finset.card_sigma, ← Finset.card_powersetCard]
      apply Finset.card_le_card_of_injOn (fun p => p.2)
  2. The projection map sends each pair (v, s) to a 2-element subset of edges of G.

    Given a pair (v, s) where s ⊆ E(v) has cardinality 2, each edge in s is incident to v and thus belongs to the graph's edge set E by SimpleGraph.incidenceFinset_subset. Therefore s ⊆ E with |s| = 2, meaning s is a valid 2-element subset of edges.

    lines 11–16

    uses SimpleGraph.incidenceFinset_subset

      · intro p hp
        simp only [Finset.coe_sigma, Set.mem_sigma_iff, Finset.mem_coe, Finset.mem_univ, true_and,
          Finset.mem_powersetCard] at hp ⊢
        exact ⟨hp.1.trans (fun e he => by
          have := (SimpleGraph.incidenceFinset_subset G p.1) he
          exact this), hp.2⟩
  3. For pairs p = (v, s) and q = (w, t) with s = t, the case v = w immediately yields p = q, reducing injectivity to ruling out v ≠ w.

    Suppose p = (v, s) and q = (w, t) have the same projection, so s = t. If v = w, then p = q holds trivially because both components coincide. Thus, establishing injectivity requires only showing that the distinct-vertex case v ≠ w is impossible.

    lines 17–26

      · intro p hp q hq hpq
        simp only [Finset.coe_sigma, Set.mem_sigma_iff, Finset.mem_coe, Finset.mem_univ, true_and,
          Finset.mem_powersetCard] at hp hq
        simp only at hpq
        obtain ⟨v, s⟩ := p
        obtain ⟨w, t⟩ := q
        simp only at hpq hp hq
        subst hpq
        by_cases hvw : v = w
        · subst hvw; rfl
  4. The case v ≠ w is impossible because two distinct edges cannot both be incident to both v and w.

    Assume for contradiction that v ≠ w. Since |s| = 2, by Finset.card_eq_two.1 we write s = {e₁, e₂} with e₁ ≠ e₂. Since s ⊆ E(v) and s ⊆ E(w), both e₁ and e₂ are incident to both v and w (using Finset.mem_insert_self, Finset.mem_insert_of_mem, Finset.mem_singleton_self, and SimpleGraph.mem_incidenceFinset). But by Sym2.mem_and_mem_iff, any edge containing two distinct vertices v and w must be the edge s(v, w). Therefore e₁ = s(v, w) = e₂, contradicting e₁ ≠ e₂.

    lines 27–40

    uses Finset.card_eq_two.1, Finset.mem_insert_self, Finset.mem_insert_of_mem, Finset.mem_singleton_self, SimpleGraph.mem_incidenceFinset, Sym2.mem_and_mem_iff

        · exfalso
          obtain ⟨e₁, e₂, hne, rfl⟩ := Finset.card_eq_two.1 hp.2
          have h1v := hp.1 (Finset.mem_insert_self _ _)
          have h2v := hp.1 (Finset.mem_insert_of_mem (Finset.mem_singleton_self _))
          have h1w := hq.1 (Finset.mem_insert_self _ _)
          have h2w := hq.1 (Finset.mem_insert_of_mem (Finset.mem_singleton_self _))
          rw [SimpleGraph.mem_incidenceFinset] at h1v h2v h1w h2w
          apply hne
          have key : ∀ e ∈ G.incidenceSet v, e ∈ G.incidenceSet w → e = s(v, w) := by
            intro e hev hew
            obtain ⟨he, hve⟩ := hev
            obtain ⟨_, hwe⟩ := hew
            exact (Sym2.mem_and_mem_iff hvw).1 ⟨hve, hwe⟩
          rw [key _ h1v h1w, key _ h2v h2w]
Finset.card_powersetCard
The number of k-element subsets of a finite set s is C(|s|, k).
SimpleGraph.card_incidenceFinset_eq_degree
The number of edges incident to a vertex v equals the degree of v.
Finset.card_sigma
The cardinality of a disjoint union of finite sets (a sigma Finset) is the sum of their cardinalities.
Finset.card_le_card_of_injOn
If a map between finite sets is injective on the source set, then the cardinality of the source is at most that of the target.
SimpleGraph.incidenceFinset_subset
The set of edges incident to a vertex v is a subset of the graph's total edge set.
Finset.card_eq_two.1
If a finite set has cardinality 2, it is of the form {x, y} for two distinct elements x ≠ y.
Finset.mem_insert_self
An element a belongs to the set obtained by inserting a into s.
Finset.mem_insert_of_mem
If an element belongs to s, it also belongs to insert b s.
Finset.mem_singleton_self
An element belongs to the singleton set containing it.
SimpleGraph.mem_incidenceFinset
An edge belongs to the finite incidence set of a vertex v if and only if it belongs to the incidence set of v.
Sym2.mem_and_mem_iff
For distinct vertices x ≠ y, an unordered pair contains both x and y if and only if it equals the pair s(x, y).

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 simple_graph_sum_choose_degree_two_le_choose_card_edgeFinset {V : Type*} [Fintype V]    [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] :    ∑ v, (G.degree v).choose 2 ≤ G.edgeFinset.card.choose 2 := by  classical  have hdeg : ∀ v, (G.degree v).choose 2 = ((G.incidenceFinset v).powersetCard 2).card := by    intro v    rw [Finset.card_powersetCard, SimpleGraph.card_incidenceFinset_eq_degree]  simp_rw [hdeg]  rw [← Finset.card_sigma, ← Finset.card_powersetCard]  apply Finset.card_le_card_of_injOn (fun p => p.2)  · intro p hp    simp only [Finset.coe_sigma, Set.mem_sigma_iff, Finset.mem_coe, Finset.mem_univ, true_and,      Finset.mem_powersetCard] at hp ⊢    exact ⟨hp.1.trans (fun e he => by      have := (SimpleGraph.incidenceFinset_subset G p.1) he      exact this), hp.2⟩  · intro p hp q hq hpq    simp only [Finset.coe_sigma, Set.mem_sigma_iff, Finset.mem_coe, Finset.mem_univ, true_and,      Finset.mem_powersetCard] at hp hq    simp only at hpq    obtain ⟨v, s⟩ := p    obtain ⟨w, t⟩ := q    simp only at hpq hp hq    subst hpq    by_cases hvw : v = w    · subst hvw; rfl    · exfalso      obtain ⟨e₁, e₂, hne, rfl⟩ := Finset.card_eq_two.1 hp.2      have h1v := hp.1 (Finset.mem_insert_self _ _)      have h2v := hp.1 (Finset.mem_insert_of_mem (Finset.mem_singleton_self _))      have h1w := hq.1 (Finset.mem_insert_self _ _)      have h2w := hq.1 (Finset.mem_insert_of_mem (Finset.mem_singleton_self _))      rw [SimpleGraph.mem_incidenceFinset] at h1v h2v h1w h2w      apply hne      have key : ∀ e ∈ G.incidenceSet v, e ∈ G.incidenceSet w → e = s(v, w) := by        intro e hev hew        obtain ⟨he, hve⟩ := hev        obtain ⟨_, hwe⟩ := hew        exact (Sym2.mem_and_mem_iff hvw).1 ⟨hve, hwe⟩      rw [key _ h1v h1w, key _ h2v h2w]
See it in the graphDiscuss this resultChallenge it