simple_graph_triangle_degree_le_choose
td_G(v) ≤ C(deg v, 2).
Statement
theorem simple_graph_triangle_degree_le_choose {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : simple_graph_triangle_degree G v ≤ (G.degree v).choose 2
- Source
- Sanity lemma for simple_graph_triangle_degree (arXiv:2610.08478 (Regular K_3-Irregular Graphs of Every Regularity at Least Nine)); used for the order bound on regular triangle-distinct graphs.
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_triangle_degreeThe triangle-degree td_G(v): the number of triangles of G containing v, i.e. the number of 2-element subsets {u, w} of the neighbourhood…
- Used by 4
- card_le_twenty_nine_of_regular_eight_triangle_distinctEvery 8-regular triangle-distinct graph has at most 29 vertices: its triangle-degrees are pairwise distinct and each is at most C(8, 2) =…
- simple_graph_eight_regular_not_card_fifteenNo 8-regular triangle-distinct simple graph exists on 15 vertices.
- simple_graph_card_le_choose_add_one_of_regular_triangle_distinctAn r-regular triangle-distinct graph has at most C(r, 2) + 1 vertices: its triangle-degrees are pairwise distinct and lie in {0, …, C(r,…
- simple_graph_regular_eight_triangle_distinct_fin_fifteen_degreesIf G is an 8-regular triangle-distinct graph on the 15 vertices {0,…,14}, then the set of its vertex triangle-degrees is exactly…
The proof, explained
The triangle degree of a vertex v counts the edges spanned by its neighborhood, formally defined as the number of adjacent 2-element subsets of neighbors. Because these adjacent pairs form a subset of all pairs of neighbors, their count is bounded by the total number of 2-element subsets of the neighborhood, which evaluates to (deg(v) choose 2).
The triangle degree of v is at most the total number of 2-element subsets of the neighbor set of v.
By definition, the triangle degree of a vertex v counts the 2-element subsets of its neighbors that are joined by an edge, represented as a filter on the collection of all 2-element subsets of N(v). Filtering any finite set can only decrease or preserve its size (Finset.card_filter_le), so this count is bounded above by the total number of 2-element subsets of N(v).
uses
Finset.card_filter_leunfold simple_graph_triangle_degree calc _ ≤ ((G.neighborFinset v).powersetCard 2).card := Finset.card_filter_le _ _
The total number of 2-element subsets of the neighbor set equals (deg(v) choose 2).
The number of size-2 subsets of a finite set of cardinality k is (k choose 2) (Finset.card_powersetCard). Rewriting with this and the fact that the neighbor set of v has size deg(v) (SimpleGraph.card_neighborFinset_eq_degree) yields the upper bound (deg(v) choose 2).
uses
Finset.card_powersetCard,SimpleGraph.card_neighborFinset_eq_degree_ = (G.degree v).choose 2 := by rw [Finset.card_powersetCard, SimpleGraph.card_neighborFinset_eq_degree]
Finset.card_filter_le- Filtering a finite set by a predicate produces a subset whose cardinality is at most that of the original set: |{x ∈ s | p(x)}| ≤ |s|.
Finset.card_powersetCard- The number of k-element subsets of a finite set s is (|s| choose k).
SimpleGraph.card_neighborFinset_eq_degree- The cardinality of the neighbor set of a vertex v equals the degree deg(v).
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_triangle_degree_le_choose {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : simple_graph_triangle_degree G v ≤ (G.degree v).choose 2 := by unfold simple_graph_triangle_degree calc _ ≤ ((G.neighborFinset v).powersetCard 2).card := Finset.card_filter_le _ _ _ = (G.degree v).choose 2 := by rw [Finset.card_powersetCard, SimpleGraph.card_neighborFinset_eq_degree]