dominating_average_stability_path_five_no_isolated
The five-vertex path has no isolated vertex.
Statement
theorem dominating_average_stability_path_five_no_isolated :
letI := dominating_average_stability_path_five_decidable
∀ w, 0 < (SimpleGraph.pathGraph 5).degree w- 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 1
- dominating_average_stability_path_five_decidableAn explicit computable adjacency decision for the five-vertex path.
The proof, explained
The theorem asserts that no vertex in the path graph on 5 vertices is isolated (each has degree at least 1). The proof rewrites the degree of a vertex into the cardinality of its neighbor finset and then finishes by exhaustive finite computation (`decide +kernel`).
The condition that every vertex has positive degree is rewritten as the condition that for each vertex, the finset of its neighbors has positive cardinality.
Rewriting with `SimpleGraph.degree` replaces the degree of a vertex with the cardinality of its neighbor finset, and `SimpleGraph.neighborFinset_eq_filter` expresses this neighbor finset as the finset of vertices adjacent to it.
uses
SimpleGraph.degree,SimpleGraph.neighborFinset_eq_filtersimp only [SimpleGraph.degree, SimpleGraph.neighborFinset_eq_filter]Every vertex in the path graph on 5 vertices has at least one neighbor. automation
Because the path graph on 5 vertices has a finite vertex type and decidable adjacency, the universal quantifier over the five vertices is verified by direct exhaustive computation in the kernel.
decide +kernel
SimpleGraph.degree- The degree of a vertex in a simple graph is the cardinality of its neighbor finset.
SimpleGraph.neighborFinset_eq_filter- In a finite graph with decidable adjacency, the neighbor finset of a vertex v consists of all vertices w adjacent to v.
- The final verification is delegated entirely to Lean's kernel via computational reflection (`decide +kernel`), which exhaustively checks the 5 vertices.
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_no_isolated : letI := dominating_average_stability_path_five_decidable ∀ w, 0 < (SimpleGraph.pathGraph 5).degree w := by simp only [SimpleGraph.degree, SimpleGraph.neighborFinset_eq_filter] decide +kernel