not_triangle_distinct_complete_fin_four
K_4 is not triangle-distinct.
Statement
theorem not_triangle_distinct_complete_fin_four :
¬ simple_graph_is_triangle_distinct (⊤ : SimpleGraph (Fin 4))- Source
- Sanity lemma for simple_graph_is_triangle_distinct (arXiv:2610.08478 (Regular K_3-Irregular Graphs of Every Regularity at Least Nine)).
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_is_triangle_distinctA graph is triangle-distinct (K_3-irregular) when its vertex triangle-degrees are pairwise distinct.
- simple_graph_triangle_degree_complete_fin_fourEvery vertex of K_4 lies in exactly 3 triangles.
- 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
We argue by contradiction: suppose the complete graph K₄ is triangle-distinct, meaning its triangle degree function is injective. Since every vertex in K₄ belongs to three triangles, any two vertices have the same triangle degree, namely 3. Injectivity then implies that the distinct vertices 0 and 1 must be equal, which is a contradiction.
It suffices to derive a contradiction from the assumption that the complete graph K₄ is triangle-distinct.
Assume, for contradiction, that the complete graph on four vertices is triangle-distinct (hypothesis h). By definition, this means that the function assigning each vertex its triangle degree is injective.
intro hThe vertices 0 and 1 of K₄ must be equal.
By simple_graph_triangle_degree_complete_fin_four, every vertex in the complete graph on four vertices has triangle degree 3. Therefore, vertex 0 and vertex 1 have identical triangle degrees (both equal to 3). Applying the assumed injectivity of the triangle degree function (h) implies 0 = 1.
uses
simple_graph_triangle_degree_complete_fin_fourhave := h ((simple_graph_triangle_degree_complete_fin_four 0).trans (simple_graph_triangle_degree_complete_fin_four 1).symm)A contradiction is reached, completing the proof. automation
The derived equality 0 = 1 is absurd because 0 ≠ 1 in Fin 4, a fact verified by direct computational evaluation (decide).
exact absurd this (by decide)
simple_graph_triangle_degree_complete_fin_four- Every vertex of the complete graph on four vertices has triangle degree 3.
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.
theorem not_triangle_distinct_complete_fin_four : ¬ simple_graph_is_triangle_distinct (⊤ : SimpleGraph (Fin 4)) := by intro h have := h ((simple_graph_triangle_degree_complete_fin_four 0).trans (simple_graph_triangle_degree_complete_fin_four 1).symm) exact absurd this (by decide)