card_le_twenty_five_of_regular_eight_triangle_distinct
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
- simple_graph_eight_regular_triangle_degree_le_twenty_fourIn any 8-regular triangle-distinct graph, the triangle-degree of every vertex is at most 24.
- simple_graph_is_triangle_distinctA graph is triangle-distinct (K_3-irregular) when its vertex triangle-degrees are pairwise distinct.
- simple_graph_triangle_degreeThe triangle-degree td_G(v): the number of triangles of G containing v, i.e. the number of 2-element subsets {u, w} of the neighbourhood…
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.
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`).
uses
Finset.card_image_of_injective,Finset.card_univhave 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]
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.
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_cardhave 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
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.
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.
- The equality of the cardinality of the discrete interval Finset.Iic 24 = {0, ..., 24} to 25 on line 16 is handled automatically by `simp`.
- The final inequality |V| ≤ 25 on line 17 is concluded via linear integer arithmetic using `omega`.
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.
/-- 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