AFTD Auto-Formalizing Theoretical Domains

not_triangle_distinct_complete_fin_four

theoremverified

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

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.

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

    line 3

      intro h
  2. The 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.

    lines 4–5

    uses simple_graph_triangle_degree_complete_fin_four

      have := h ((simple_graph_triangle_degree_complete_fin_four 0).trans
        (simple_graph_triangle_degree_complete_fin_four 1).symm)
  3. 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).

    line 6

      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

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