card_le_twenty_nine_of_regular_eight_triangle_distinct
Every 8-regular triangle-distinct graph has at most 29 vertices: its triangle-degrees are pairwise distinct and each is at most C(8, 2) = 28.
Statement
theorem card_le_twenty_nine_of_regular_eight_triangle_distinct {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hreg : G.IsRegularOfDegree 8) (htd : simple_graph_is_triangle_distinct G) : Fintype.card V ≤ 29
- Source
- Pigeonhole bound towards OP-123 (arXiv:2610.08478, Sec. 1). Its recorded dependency on the unproved exists_regular_eight_triangle_distinct blocks the offline build; the r = 8 case of the proved simple_graph_card_le_choose_add_one_of_regular_triangle_distinct is the same bound.
- Verified
- 13 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…
The proof, explained
The proof bounds the number of vertices by viewing the triangle-degree function as an injection into a small set of integers. Since G is 8-regular, any vertex has 8 neighbors and can participate in at most C(8, 2) = 28 triangles, meaning every triangle-degree is an integer in {0, ..., 28}. Because G is triangle-distinct, distinct vertices have distinct triangle-degrees, so the triangle-degree map is injective; by the pigeonhole principle, the graph can have at most 29 vertices.
For every vertex v, its triangle-degree is at most 28, so it belongs to {0, ..., 28} (Finset.range 29).
For any vertex v, its triangle-degree is bounded by C(deg(v), 2) using simple_graph_triangle_degree_le_choose. Since G is 8-regular (hreg v), this bound is C(8, 2). A direct calculation (decide) evaluates C(8, 2) = 28. Using Finset.mem_range to rephrase membership in Finset.range 29 as being strictly less than 29, linear arithmetic (omega) closes the goal from triangle-degree ≤ 28.
uses
simple_graph_triangle_degree_le_choose,Finset.mem_rangehave hmaps : ∀ v ∈ (Finset.univ : Finset V), simple_graph_triangle_degree G v ∈ Finset.range 29 := by intro v _ have h1 := simple_graph_triangle_degree_le_choose G v rw [hreg v] at h1 simp only [Finset.mem_range] have : (8 : ℕ).choose 2 = 28 := by decide omega
The vertex set of G has cardinality at most 29.
By hypothesis htd, the triangle-degree map is injective on the entire vertex set. Applying Finset.card_le_card_of_injOn to this map from Finset.univ into Finset.range 29 shows that the number of vertices |Finset.univ| is at most |Finset.range 29|. Simplifying cardinalities (simpa) yields |V| ≤ 29.
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- In any simple graph, the triangle-degree of a vertex v is at most C(degree(v), 2), the number of pairs of its neighbors.
Finset.mem_range- A natural number m belongs to Finset.range n if and only if m < n.
Finset.card_le_card_of_injOn- If a function maps a finite set s into a finite set t injectively, then |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 card_le_twenty_nine_of_regular_eight_triangle_distinct {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hreg : G.IsRegularOfDegree 8) (htd : simple_graph_is_triangle_distinct G) : Fintype.card V ≤ 29 := by have hmaps : ∀ v ∈ (Finset.univ : Finset V), simple_graph_triangle_degree G v ∈ Finset.range 29 := by intro v _ have h1 := simple_graph_triangle_degree_le_choose G v rw [hreg v] at h1 simp only [Finset.mem_range] have : (8 : ℕ).choose 2 = 28 := by decide omega have := Finset.card_le_card_of_injOn _ hmaps (htd.injOn) simpa using this