AFTD Auto-Formalizing Theoretical Domains

regular_eight_triangle_distinct_card_ge_fifteen

theoremverified

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
Used by 1

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.

  1. 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.

    lines 4–8

    uses G.degree_lt_card_verts

      obtain ⟨v⟩ := ‹Nonempty V›
      have h9 : 9 ≤ Fintype.card V := by
        have := G.degree_lt_card_verts v
        rw [hreg v] at this
        omega
  2. 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.

    lines 9–10

    uses simple_graph_compl_regular_triangle_distinct

      obtain ⟨hcreg, hctd⟩ :=
        simple_graph_compl_regular_triangle_distinct G 8 (Fintype.card V) rfl hreg htd
  3. 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.

    line 11

    uses simple_graph_card_le_choose_add_one_of_regular_triangle_distinct

      have hb := simple_graph_card_le_choose_add_one_of_regular_triangle_distinct Gᶜ _ hcreg hctd
  4. The 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.

    lines 12–14

    uses Nat.choose

      by_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

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]
See it in the graphDiscuss this resultChallenge it