not_simple_graph_is_star_like_complete_three
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
- simple_graph_is_star_likeG is star-like: every vertex is either a leaf (degree one) or an l-stem with 1 ≤ l ≤ 2.
- simple_graph_leaf_neighbor_countThe number of leaf neighbours (neighbours of degree one) of a vertex v; v is an l-stem when this number is l ≥ 1.
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.
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.
unfold simple_graph_is_star_like simple_graph_leaf_neighbor_count; decide
- The goal is closed by `decide`, which performs finite exhaustive computation over the three vertices of `Fin 3` to verify that the condition fails.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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