dominating_average_stability_path_five_delete_endpoint
Deleting an endpoint from the five-vertex path leaves a star-like induced graph.
Statement
theorem dominating_average_stability_path_five_delete_endpoint :
letI := dominating_average_stability_path_five_decidable
simple_graph_is_star_like
((SimpleGraph.pathGraph 5).induce (({0} : Finset (Fin 5))ᶜ : Set (Fin 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.
- Used by 1
- dominating_average_stability_path_five_deletionThe minimum star-like vertex deletion distance of the five-vertex path is exactly1.
The proof, explained
Deleting an endpoint from the five-vertex path $P_5$ leaves an induced path $P_4$ on four vertices. A graph is star-like when every vertex either has degree 1 or is adjacent to between 1 and 2 leaves. After expanding this condition into explicit expressions on finite sets of adjacent vertices, Lean's kernel verifies the claim by exhaustive evaluation over all four vertices.
The condition for the induced subgraph to be star-like is expanded into an explicit statement about sets of adjacent vertices.
Unfolding the definitions of a star-like graph (`simple_graph_is_star_like`) and leaf-neighbor count (`simple_graph_leaf_neighbor_count`), and rewriting vertex degrees with `SimpleGraph.degree` and neighborhoods with `SimpleGraph.neighborFinset_eq_filter`, expresses the goal as a purely combinatorial condition: for every vertex in the four-vertex induced subgraph, either its degree is 1 or its number of leaf neighbors is between 1 and 2.
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]
Every vertex in the induced subgraph satisfies the star-like condition. automation
The induced subgraph has only four vertices (vertices 1 through 4 of the original five-vertex path) and its adjacency relation is decidable. The `decide +kernel` tactic evaluates the finite universal quantification exhaustively: endpoints 1 and 4 have degree 1, while internal vertices 2 and 3 each have degree 2 and are adjacent to exactly one leaf.
decide +kernel
SimpleGraph.degree- The degree of a vertex is defined as the cardinality of its neighborhood finset.
SimpleGraph.neighborFinset_eq_filter- The neighborhood finset of a vertex in a finite graph consists of all vertices adjacent to it.
- The proof delegates the verification to Lean's kernel via computational reflection (`decide +kernel`), which checks all four vertices exhaustively rather than writing out the case analysis.
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_delete_endpoint : letI := dominating_average_stability_path_five_decidable simple_graph_is_star_like ((SimpleGraph.pathGraph 5).induce (({0} : Finset (Fin 5))ᶜ : Set (Fin 5))) := by unfold simple_graph_is_star_like simple_graph_leaf_neighbor_count simp only [SimpleGraph.degree, SimpleGraph.neighborFinset_eq_filter] decide +kernel