AFTD Auto-Formalizing Theoretical Domains

simple_graph_leaf_neighbor_count_complete_two

theoremverified

In K₂, each vertex has exactly one leaf neighbour.

Statement

theorem simple_graph_leaf_neighbor_count_complete_two :
    simple_graph_leaf_neighbor_count (⊤ : SimpleGraph (Fin 2)) 0 = 1
Source
Sanity check of the definitions of arXiv:2610.11446 (On the local average order of dominating sets).
Verified
09 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

In the complete graph on two vertices $K_2$, vertex $0$ is adjacent only to vertex $1$, which has degree $1$. Unfolding the definition of the leaf-neighbour count reduces the theorem to a finite verification, which is closed by computational evaluation.

  1. In $K_2$, vertex $0$ has exactly one leaf neighbour. automation

    Unfolding the definition of `simple_graph_leaf_neighbor_count` rephrases the goal as checking that the cardinality of the set of neighbours of vertex $0$ with degree $1$ is equal to $1$. Because the complete graph on `Fin 2` is finite and concrete, this is a decidable proposition: vertex $0$ has only vertex $1$ as a neighbour, and vertex $1$ has degree $1$. The `decide` tactic evaluates this finite computation directly to close the goal.

    line 3

      unfold simple_graph_leaf_neighbor_count; 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_leaf_neighbor_count_complete_two :    simple_graph_leaf_neighbor_count (⊤ : SimpleGraph (Fin 2)) 0 = 1 := by  unfold simple_graph_leaf_neighbor_count; decide
See it in the graphDiscuss this resultChallenge it