AFTD Auto-Formalizing Theoretical Domains

simple_graph_card_le_choose_add_one_of_regular_triangle_distinct

theoremverified

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

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.

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

    lines 5–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 (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
  2. 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.

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

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