simple_graph_card_le_choose_add_one_of_regular_triangle_distinct
An 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, 2)}.
Statement
theorem simple_graph_card_le_choose_add_one_of_regular_triangle_distinct {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (r : ℕ) (hreg : G.IsRegularOfDegree r) (htd : simple_graph_is_triangle_distinct G) : Fintype.card V ≤ r.choose 2 + 1
- Source
- Pigeonhole bound used for OP-123 (arXiv:2610.08478 (Regular K_3-Irregular Graphs of Every Regularity at Least Nine), Sec. 1).
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_is_triangle_distinctA graph is triangle-distinct (K_3-irregular) when its vertex triangle-degrees are pairwise distinct.
- simple_graph_triangle_degree_le_choosetd_G(v) ≤ C(deg v, 2).
- 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 1
- regular_eight_triangle_distinct_card_ge_fifteenEvery 8-regular triangle-distinct graph with at least one vertex has at least 15 vertices: its complement is (n − 9)-regular and…
The proof, explained
The proof applies the pigeonhole principle to the triangle-degree function on the vertices. In an r-regular graph, every vertex has degree r, so each vertex can be part of at most C(r, 2) triangles. Because the graph is triangle-distinct, no two vertices share the same triangle-degree. The triangle-degree map is therefore an injection from the vertex set into {0, …, C(r, 2)}, forcing the number of vertices to be at most C(r, 2) + 1.
For every vertex v, its triangle-degree is at most C(r, 2), so it belongs to {0, …, C(r, 2)}.
For an arbitrary vertex v, the number of triangles containing v is at most C(deg(v), 2) by simple_graph_triangle_degree_le_choose. Since the graph is r-regular (hreg), deg(v) = r, which bounds the triangle-degree by C(r, 2). Rewriting with Finset.mem_range expresses membership in the range of C(r, 2) + 1 as being strictly less than C(r, 2) + 1, which holds by linear arithmetic (omega).
uses
simple_graph_triangle_degree_le_choose,Finset.mem_rangehave hmaps : ∀ v ∈ (Finset.univ : Finset V), simple_graph_triangle_degree G v ∈ Finset.range (r.choose 2 + 1) := by intro v _ have h1 := simple_graph_triangle_degree_le_choose G v rw [hreg v] at h1 rw [Finset.mem_range] omega
The number of vertices |V| is at most C(r, 2) + 1.
Because G is triangle-distinct (htd), the triangle-degree map is injective. Since it maps the finite set of all vertices into the range {0, …, C(r, 2)}, the pigeonhole principle for finite sets (Finset.card_le_card_of_injOn) implies that the number of vertices cannot exceed the size of the codomain, which is C(r, 2) + 1. Simplifying the cardinalities (simpa) concludes the proof.
uses
Finset.card_le_card_of_injOnhave := Finset.card_le_card_of_injOn _ hmaps htd.injOn simpa using this
simple_graph_triangle_degree_le_choose- The triangle-degree of any vertex v in a graph is at most the number of pairs of its neighbors, C(deg(v), 2).
Finset.mem_range- A natural number m belongs to Finset.range n if and only if m < n.
Finset.card_le_card_of_injOn- An injective map from a finite set s to a finite set t implies |s| ≤ |t|.
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_card_le_choose_add_one_of_regular_triangle_distinct {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (r : ℕ) (hreg : G.IsRegularOfDegree r) (htd : simple_graph_is_triangle_distinct G) : Fintype.card V ≤ r.choose 2 + 1 := by have hmaps : ∀ v ∈ (Finset.univ : Finset V), simple_graph_triangle_degree G v ∈ Finset.range (r.choose 2 + 1) := by intro v _ have h1 := simple_graph_triangle_degree_le_choose G v rw [hreg v] at h1 rw [Finset.mem_range] omega have := Finset.card_le_card_of_injOn _ hmaps htd.injOn simpa using this