AFTD Auto-Formalizing Theoretical Domains

card_le_twenty_nine_of_regular_eight_triangle_distinct

theoremverified

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

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.

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

    lines 4–11

    uses simple_graph_triangle_degree_le_choose, Finset.mem_range

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

    lines 12–13

    uses Finset.card_le_card_of_injOn

      have := 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

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