simple_graph_is_star_like_complete_two
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
- 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.
- Used by 1
- dominating_average_star_like_vertex_stability_of_card_twoFor every finite simple graph G on 2 vertices with no isolated vertex, the stability inequality 5 d_*(G) ≤ 51 (2·2/3 - avd(G)) holds.
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.
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`).
unfold simple_graph_is_star_like simple_graph_leaf_neighbor_count; decide
- The proof relies on computational reflection (`decide`) to check the predicate across all vertices of the two-element graph.
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 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