regular_eight_triangle_distinct_card_ge_fifteen
Every 8-regular triangle-distinct graph with at least one vertex has at least 15 vertices: its complement is (n − 9)-regular and triangle-distinct, so n ≤ C(n − 9, 2) + 1, which fails for 9 ≤ n ≤ 14.
Statement
theorem regular_eight_triangle_distinct_card_ge_fifteen {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V] (G : SimpleGraph V) [DecidableRel G.Adj] (hreg : G.IsRegularOfDegree 8) (htd : simple_graph_is_triangle_distinct G) : 15 ≤ Fintype.card V
- Source
- Partial result towards OP-123 (arXiv:2610.08478 (Regular K_3-Irregular Graphs of Every Regularity at Least Nine), Lemma 2.1 complementation and Sec. 1); the earlier work cited there narrows the regularity-8 case further, to six orders.
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_compl_regular_triangle_distinctIf G is an r-regular triangle-distinct graph on N vertices, its complement is an (N − r − 1)-regular triangle-distinct graph.
- 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_is_triangle_distinctA graph is triangle-distinct (K_3-irregular) when its vertex triangle-degrees are pairwise distinct.
- Used by 1
- regular_eight_triangle_distinct_card_ge_sixteenEvery nonempty 8-regular triangle-distinct graph has at least 16 vertices, tightening the previous lower bound of 15.
The proof, explained
Since the graph is 8-regular and nonempty, every vertex has degree 8 < |V|, establishing the lower bound |V| ≥ 9. Its complement graph is (|V| − 9)-regular and triangle-distinct, which yields the upper bound |V| ≤ C(|V| − 9, 2) + 1. A finite case analysis over the integers 9 ≤ |V| ≤ 14 shows that none satisfies this bound, so |V| must be at least 15.
The graph has at least 9 vertices (|V| ≥ 9).
Since V is nonempty, we can pick a vertex v ∈ V. In any simple graph, the degree of a vertex is strictly less than the total number of vertices. Since G is 8-regular, the degree of v is 8, which implies 8 < |V|, and therefore |V| ≥ 9.
uses
G.degree_lt_card_vertsobtain ⟨v⟩ := ‹Nonempty V› have h9 : 9 ≤ Fintype.card V := by have := G.degree_lt_card_verts v rw [hreg v] at this omega
The complement graph Gᶜ is (|V| − 9)-regular and triangle-distinct.
Applying simple_graph_compl_regular_triangle_distinct to the 8-regular triangle-distinct graph G on |V| vertices shows that its complement graph Gᶜ is regular of degree |V| − 8 − 1 = |V| − 9 and remains triangle-distinct.
uses
simple_graph_compl_regular_triangle_distinctobtain ⟨hcreg, hctd⟩ := simple_graph_compl_regular_triangle_distinct G 8 (Fintype.card V) rfl hreg htd
The number of vertices satisfies |V| ≤ C(|V| − 9, 2) + 1.
Applying simple_graph_card_le_choose_add_one_of_regular_triangle_distinct to the complement graph Gᶜ, any r-regular triangle-distinct graph has at most C(r, 2) + 1 vertices. Since Gᶜ has degree r = |V| − 9, this gives the upper bound |V| ≤ C(|V| − 9, 2) + 1.
uses
simple_graph_card_le_choose_add_one_of_regular_triangle_distincthave hb := simple_graph_card_le_choose_add_one_of_regular_triangle_distinct Gᶜ _ hcreg hctdThe graph has at least 15 vertices (|V| ≥ 15).
Assume for contradiction that |V| < 15. Combined with |V| ≥ 9, this leaves only the cases |V| ∈ {9, 10, 11, 12, 13, 14}. Evaluating the inequality n ≤ C(n − 9, 2) + 1 for each of these six integers yields a contradiction in every case: 9 ≤ 1, 10 ≤ 1, 11 ≤ 2, 12 ≤ 4, 13 ≤ 7, and 14 ≤ 11 are all false. Therefore, |V| ≥ 15.
uses
Nat.chooseby_contra hlt push Not at hlt interval_cases h : Fintype.card V <;> simp_all [Nat.choose]
G.degree_lt_card_verts- In any finite simple graph, the degree of any vertex is strictly less than the total number of vertices in the graph.
simple_graph_compl_regular_triangle_distinct- If a graph on N vertices is r-regular and triangle-distinct, then its complement graph is (N − r − 1)-regular and triangle-distinct.
simple_graph_card_le_choose_add_one_of_regular_triangle_distinct- Every r-regular triangle-distinct graph on a finite vertex set has at most C(r, 2) + 1 vertices.
Nat.choose- The binomial coefficient C(n, k), representing the number of k-element subsets of an n-element set.
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 regular_eight_triangle_distinct_card_ge_fifteen {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V] (G : SimpleGraph V) [DecidableRel G.Adj] (hreg : G.IsRegularOfDegree 8) (htd : simple_graph_is_triangle_distinct G) : 15 ≤ Fintype.card V := by obtain ⟨v⟩ := ‹Nonempty V› have h9 : 9 ≤ Fintype.card V := by have := G.degree_lt_card_verts v rw [hreg v] at this omega obtain ⟨hcreg, hctd⟩ := simple_graph_compl_regular_triangle_distinct G 8 (Fintype.card V) rfl hreg htd have hb := simple_graph_card_le_choose_add_one_of_regular_triangle_distinct Gᶜ _ hcreg hctd by_contra hlt push Not at hlt interval_cases h : Fintype.card V <;> simp_all [Nat.choose]