AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_star_like_complete_two

theoremverified

K₂ is star-like.

Statement

theorem simple_graph_is_star_like_complete_two : simple_graph_is_star_like (⊤ : SimpleGraph (Fin 2))
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
Used by 1

The proof, explained

A simple graph is star-like if every vertex is either a leaf (degree 1) or has one or two leaf neighbors. For the complete graph on two vertices $K_2$, each vertex has degree 1, so the condition holds vacuously for all vertices. The proof unfolds the relevant definitions and closes the goal by computational evaluation over the two vertices.

  1. The complete graph $K_2$ satisfies the definition of being star-like. automation

    We unfold the definitions of `simple_graph_is_star_like` and `simple_graph_leaf_neighbor_count`. This leaves the claim that every vertex in the complete graph on two vertices either has degree 1 or has 1 to 2 leaf neighbors. Since the graph has only two vertices (each of degree 1), this is a finite decidable property which is discharged by computational evaluation (`decide`).

    line 2

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