AFTD Auto-Formalizing Theoretical Domains

card_le_twenty_five_of_regular_eight_triangle_distinct

theoremverified

Every 8-regular triangle-distinct graph has at most 25 vertices, since its vertex triangle-degrees are pairwise distinct elements of {0, ..., 24}.

Statement

theorem card_le_twenty_five_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 ≤ 25
Source
step towards regular_eight_triangle_distinct_witness
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The proof applies the pigeonhole principle to the vertex triangle-degrees of the graph. Because the graph is triangle-distinct, the function assigning each vertex its triangle degree is injective, so the number of vertices equals the number of distinct triangle degrees. Since every vertex in an 8-regular triangle-distinct graph has triangle degree at most 24, all triangle degrees lie in {0, ..., 24}, a set of 25 values, which bounds the number of vertices by 25.

  1. The image of the vertex set under the triangle-degree function has cardinality |V|.

    By definition of a triangle-distinct graph (`htd`), the mapping sending each vertex v to its triangle degree is injective. Since an injective map preserves the cardinality of finite sets (via `Finset.card_image_of_injective`), the image of Finset.univ under this map has cardinality equal to |Finset.univ|, which is the number of vertices |V| (via `Finset.card_univ`).

    lines 6–8

    uses Finset.card_image_of_injective, Finset.card_univ

      have hinj : Function.Injective (fun v => simple_graph_triangle_degree G v) := htd
      have h1 : (Finset.univ.image (fun v => simple_graph_triangle_degree G v)).card = Fintype.card V := by
        rw [Finset.card_image_of_injective _ hinj, Finset.card_univ]
  2. The image of the vertex set under the triangle-degree function has cardinality at most 25.

    First, lines 10–14 establish that the image of the triangle-degree function is a subset of the interval {0, ..., 24} (`Finset.Iic 24`): any element x in the image is the triangle degree of some vertex v, and by `simple_graph_eight_regular_triangle_degree_le_twenty_four`, that triangle degree is at most 24. Next, lines 15–16 conclude by monotonicity of cardinality (`Finset.card_le_card`) that the size of the image is at most the size of {0, ..., 24}, which simplifies to 25.

    lines 9–16

    uses Finset.mem_image, Finset.mem_univ, true_and, Finset.mem_Iic.mpr, simple_graph_eight_regular_triangle_degree_le_twenty_four, Finset.card_le_card

      have h2 : (Finset.univ.image (fun v => simple_graph_triangle_degree G v)).card ≤ 25 := by
        have hsub : (Finset.univ.image (fun v => simple_graph_triangle_degree G v)) ⊆ Finset.Iic 24 := by
          intro x hx
          simp only [Finset.mem_image, Finset.mem_univ, true_and] at hx
          obtain ⟨v, rfl⟩ := hx
          exact Finset.mem_Iic.mpr (simple_graph_eight_regular_triangle_degree_le_twenty_four G hreg htd v)
        calc (Finset.univ.image (fun v => simple_graph_triangle_degree G v)).card ≤ (Finset.Iic 24).card := Finset.card_le_card hsub
          _ = 25 := by simp
  3. The graph has at most 25 vertices (|V| ≤ 25).

    Linear arithmetic (`omega`) combines the equality |V| = card(image) from the first step and the upper bound card(image) ≤ 25 from the second step to conclude |V| ≤ 25.

    line 17

      omega
Finset.card_image_of_injective
An injective function maps a finite set to an image with the same number of elements.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type itself.
Finset.mem_image
An element belongs to the image of a finset under a function if and only if it is the image of some element in that finset.
Finset.mem_univ
Every element of a finite type is an element of its universal finset.
true_and
The conjunction of True with any proposition p is logically equivalent to p.
Finset.mem_Iic.mpr
If x ≤ a, then x belongs to the closed lower interval Finset.Iic a.
simple_graph_eight_regular_triangle_degree_le_twenty_four
In an 8-regular triangle-distinct graph, every vertex has triangle degree at most 24.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most the cardinality of the other 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

/-- Every 8-regular triangle-distinct graph has at most 25 vertices. -/theorem card_le_twenty_five_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 ≤ 25 := by  have hinj : Function.Injective (fun v => simple_graph_triangle_degree G v) := htd  have h1 : (Finset.univ.image (fun v => simple_graph_triangle_degree G v)).card = Fintype.card V := by    rw [Finset.card_image_of_injective _ hinj, Finset.card_univ]  have h2 : (Finset.univ.image (fun v => simple_graph_triangle_degree G v)).card ≤ 25 := by    have hsub : (Finset.univ.image (fun v => simple_graph_triangle_degree G v)) ⊆ Finset.Iic 24 := by      intro x hx      simp only [Finset.mem_image, Finset.mem_univ, true_and] at hx      obtain ⟨v, rfl⟩ := hx      exact Finset.mem_Iic.mpr (simple_graph_eight_regular_triangle_degree_le_twenty_four G hreg htd v)    calc (Finset.univ.image (fun v => simple_graph_triangle_degree G v)).card ≤ (Finset.Iic 24).card := Finset.card_le_card hsub      _ = 25 := by simp  omega
See it in the graphDiscuss this resultChallenge it