AFTD Auto-Formalizing Theoretical Domains

not_simple_graph_is_star_like_complete_three

theoremverified

K₃ is not star-like (no vertex is a leaf or has a leaf neighbour).

Statement

theorem not_simple_graph_is_star_like_complete_three :
    ¬ simple_graph_is_star_like (⊤ : SimpleGraph (Fin 3))
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 2

The proof, explained

By definition, a graph is star-like if every vertex either has degree 1 or has between 1 and 2 neighbours of degree 1. In the complete graph $K_3$, every vertex has degree 2, meaning there are no leaves and no vertex has a leaf neighbour. The proof unfolds these definitions and completes the verification by finite computation on the three vertices.

  1. The complete graph $K_3$ is not star-like. automation

    Unfolding the definitions of `simple_graph_is_star_like` and `simple_graph_leaf_neighbor_count` reduces the theorem to showing that not every vertex in $K_3$ has degree 1 or between 1 and 2 leaf neighbours. Because $K_3$ on $\mathrm{Fin}\ 3$ is a finite graph, this negated universally quantified condition is purely computational: every vertex has degree 2 and zero leaf neighbours, so the `decide` tactic checks and refutes it by finite evaluation.

    line 3

      unfold simple_graph_is_star_like 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 not_simple_graph_is_star_like_complete_three :    ¬ simple_graph_is_star_like (⊤ : SimpleGraph (Fin 3)) := by  unfold simple_graph_is_star_like simple_graph_leaf_neighbor_count; decide
See it in the graphDiscuss this resultChallenge it