AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_degree_complete_fin_four

theoremverified

Every vertex of K_4 lies in exactly 3 triangles.

Statement

theorem simple_graph_triangle_degree_complete_fin_four (v : Fin 4) :
    simple_graph_triangle_degree (⊤ : SimpleGraph (Fin 4)) v = 3
Source
Sanity lemma for simple_graph_triangle_degree (arXiv:2610.08478 (Regular K_3-Irregular Graphs of Every Regularity at Least Nine)).
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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…
Used by 2

The proof, explained

The proof generalizes over the vertex v to obtain a universal statement over the four-element type Fin 4. Since the graph is finite and complete and all operations in the definition of triangle degree are decidable, the goal is resolved by exhaustive finite computation via `decide`.

  1. Every vertex of the complete graph K_4 has triangle degree 3. automation

    We first revert the arbitrary vertex v into a universally quantified variable, resulting in the goal ∀ (v : Fin 4), simple_graph_triangle_degree ⊤ v = 3. Because Fin 4 is a finite type and all graph operations (neighbor sets, subsets of size 2, and adjacency checks) are computable, this universal claim is decidable and is verified by exhaustive computation via `decide`.

    line 3

      revert v; decide

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_triangle_degree_complete_fin_four (v : Fin 4) :    simple_graph_triangle_degree (⊤ : SimpleGraph (Fin 4)) v = 3 := by  revert v; decide
See it in the graphDiscuss this resultChallenge it