dominating_average_stability_path_five_not_star
The five-vertex path is not star-like.
Statement
theorem dominating_average_stability_path_five_not_star :
letI := dominating_average_stability_path_five_decidable
¬ simple_graph_is_star_like (SimpleGraph.pathGraph 5)- Source
- Finite sharpness certificate for the original OP-544 / IN-263 stability question. arXiv:2208.10475v2 Theorem2.9 supplies the extremal background. This formalizes the already computationally observed P5 obstruction to a smaller coefficient, not a proof of the universal bound or a research advance.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- dominating_average_stability_path_five_decidableAn explicit computable adjacency decision for the five-vertex path.
The proof, explained
A graph is defined to be star-like if every vertex is either a leaf (degree 1) or has between 1 and 2 leaf neighbors. In the path graph on five vertices, the central vertex has degree 2 and both of its neighbors also have degree 2, so it has zero leaf neighbors, violating the star-like condition. The proof unfolds the definitions into explicit finite-set computations and disproves the property by direct kernel evaluation.
The star-like condition on the 5-vertex path is rewritten as an explicit finite-set condition over the vertices of Fin 5.
By definition, a graph is star-like if every vertex either has degree 1 or has between 1 and 2 leaf neighbors (neighbors of degree 1). Unfolding the definitions `simple_graph_is_star_like` and `simple_graph_leaf_neighbor_count`, and rewriting degrees and neighbor finsets using `SimpleGraph.degree` and `SimpleGraph.neighborFinset_eq_filter`, expresses the property purely as a boolean condition on the adjacencies of the 5 vertices.
uses
SimpleGraph.degree,SimpleGraph.neighborFinset_eq_filterunfold simple_graph_is_star_like simple_graph_leaf_neighbor_count simp only [SimpleGraph.degree, SimpleGraph.neighborFinset_eq_filter]
The five-vertex path graph is not star-like. automation
Because the vertex set `Fin 5` is finite and graph adjacency is decidable, the universal condition reduces to checking each vertex. The central vertex (index 2) has degree 2 and no leaf neighbors (its neighbors both have degree 2), violating the condition. Lean's kernel evaluates the full finite boolean statement to false, proving the negation.
decide +kernel
SimpleGraph.degree- The degree of a vertex in a graph is the cardinality of its neighborhood.
SimpleGraph.neighborFinset_eq_filter- The neighborhood finset of a vertex in a finite graph equals the set of all vertices adjacent to it.
- The proof relies on direct kernel reduction (`decide +kernel`) to evaluate the truth value of a decidable proposition on a finite graph by exhaustive computation.
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.
set_option maxRecDepth 10000set_option maxHeartbeats 1000000theorem dominating_average_stability_path_five_not_star : letI := dominating_average_stability_path_five_decidable ¬ simple_graph_is_star_like (SimpleGraph.pathGraph 5) := by unfold simple_graph_is_star_like simple_graph_leaf_neighbor_count simp only [SimpleGraph.degree, SimpleGraph.neighborFinset_eq_filter] decide +kernel