simple_graph_sum_choose_degree_two_le_choose_card_edgeFinset
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
- simple_graph_is_tree_card_sub_two_le_sum_choose_degree_le_chooseFor a tree T on k ≥ 2 vertices, σ₂(T) = ∑_v C(d_T(v),2) satisfies k − 2 ≤ σ₂(T) ≤ C(k−1,2).
- simple_graph_is_tree_sum_choose_degree_eq_iff_starFor a tree T on k ≥ 2 vertices, σ₂(T) = C(k−1,2) if and only if T is a star K_{1,k−1}: some vertex r is adjacent to every other vertex and…
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.
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.
uses
Finset.card_powersetCard,SimpleGraph.card_incidenceFinset_eq_degree,Finset.card_sigma,Finset.card_le_card_of_injOnclassical 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)
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.
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⟩
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.
· 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
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₂.
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).
- In Lean's SimpleGraph library, edges are represented as unordered pairs of vertices of type Sym2 V, denoted s(v, w). The geometric fact that two distinct vertices determine at most one edge is captured via Sym2.mem_and_mem_iff.
- The sum ∑ v, C(d(v), 2) is represented formally as the cardinality of a sigma Finset, which packs each vertex v together with a 2-element subset of its incident edges.
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 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]