dominating_average_stability_path_five_deletion
The minimum star-like vertex deletion distance of the five-vertex path is exactly1.
Statement
theorem dominating_average_stability_path_five_deletion :
letI := dominating_average_stability_path_five_decidable
simple_graph_star_like_deletion_number (SimpleGraph.pathGraph 5) = 1- 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 5
- simple_graph_star_like_deletion_numberThe star-like deletion number d_*(G) of a finite simple graph G is the minimum cardinality of a subset X of vertices such that the induced…
- 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.
- dominating_average_stability_path_five_delete_endpointDeleting an endpoint from the five-vertex path leaves a star-like induced graph.
- Used by 1
- dominating_average_stability_constant_lower_boundAny multiplicative stability coefficient valid on the five-vertex path is at least51/5. This is a necessary constant, not the universal…
The proof, explained
The theorem is proved by matching upper and lower bounds using antisymmetry of the ordering on ℕ. Deleting the single endpoint vertex 0 leaves a star-like path of length 4, which establishes that the minimum deletion distance is at most 1. For the lower bound, any deletion set of size less than 1 would have to be empty, but exhaustive finite verification confirms that the full five-vertex path is not star-like, ruling out 0.
The star-like deletion number is rephrased as the infimum of the sizes of all deletion sets that leave a star-like graph.
We activate decidability of adjacency for the 5-vertex path and unfold the definition of the star-like deletion number, formulating the goal as showing that the infimum of the set of cardinalities of star-like deletion sets equals 1.
letI := dominating_average_stability_path_five_decidable change simple_graph_star_like_deletion_number (SimpleGraph.pathGraph 5) = 1 unfold simple_graph_star_like_deletion_number
1 is the size of a valid deletion set, certifying that the deletion number is at most 1.
Deleting the single endpoint vertex 0 leaves a 4-vertex path, which is star-like by the auxiliary lemma dominating_average_stability_path_five_delete_endpoint. Since |{0}| = 1, 1 belongs to the set of valid deletion sizes.
uses
dominating_average_stability_path_five_delete_endpointhave hmem : 1 ∈ {k : ℕ | ∃ X : Finset (Fin 5), simple_graph_is_star_like ((SimpleGraph.pathGraph 5).induce (Xᶜ : Set (Fin 5))) ∧ X.card = k} := ⟨{0}, dominating_average_stability_path_five_delete_endpoint, by simp⟩
It suffices to show that every star-like deletion set has cardinality at least 1.
By antisymmetry (le_antisymm), since 1 is an element of the set, the infimum is at most 1 (Nat.sInf_le). By le_csInf, proving the lower bound 1 ≤ sInf reduces to showing that every deletion set leaving a star-like graph has size at least 1.
uses
le_antisymm,Nat.sInf_le,le_csInfapply le_antisymm (Nat.sInf_le hmem) apply le_csInf ⟨1,hmem⟩
Any deletion set of cardinality strictly less than 1 must be the empty set.
Let X be a vertex subset such that deleting X leaves a star-like graph. For contradiction, suppose |X| < 1. By integer arithmetic, |X| = 0, and because only the empty set has cardinality 0 (Finset.card_eq_zero.mp), we obtain X = ∅.
uses
Finset.card_eq_zero.mprintro k ⟨X,hX,rfl⟩ by_contra hbad have hxzero : X.card = 0 := by omega have hx : X = ∅ := Finset.card_eq_zero.mp hxzero subst X
The original five-vertex path P₅ (deleting the empty set) is not star-like. automation
Unfolding the definitions of star-like graphs and leaf-neighbor counts, Lean evaluates the condition on the finite graph P₅ by kernel computation (decide +kernel), establishing that P₅ itself fails to be star-like.
uses
SimpleGraph.degree,SimpleGraph.neighborFinset_eq_filterhave hempty : ¬ simple_graph_is_star_like ((SimpleGraph.pathGraph 5).induce ((∅ : 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
A contradiction is reached, completing the proof.
The assumption that deleting the empty set leaves a star-like graph contradicts the computation showing that P₅ is not star-like.
exact hempty hX
dominating_average_stability_path_five_delete_endpoint- the subgraph of the 5-vertex path obtained by removing vertex 0 is star-like
le_antisymm- if a ≤ b and b ≤ a, then a = b in any partial order
Nat.sInf_le- for any set of natural numbers s and any element m ∈ s, the infimum sInf s is at most m
le_csInf- in a conditionally complete lattice, if s is nonempty and a is a lower bound for s, then a ≤ sInf s
Finset.card_eq_zero.mp- a finite set has cardinality zero only if it is empty
SimpleGraph.degree- the degree of a vertex in a simple graph is the cardinality of its set of neighbors
SimpleGraph.neighborFinset_eq_filter- the finset of neighbors of a vertex v equals the set of vertices adjacent to v
- The fact that the five-vertex path $P_5$ is not star-like is verified computationally by Lean's kernel via `decide +kernel`, which exhaustively tests all vertices of the finite 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.
set_option maxRecDepth 10000set_option maxHeartbeats 1000000theorem dominating_average_stability_path_five_deletion : letI := dominating_average_stability_path_five_decidable simple_graph_star_like_deletion_number (SimpleGraph.pathGraph 5) = 1 := by letI := dominating_average_stability_path_five_decidable change simple_graph_star_like_deletion_number (SimpleGraph.pathGraph 5) = 1 unfold simple_graph_star_like_deletion_number have hmem : 1 ∈ {k : ℕ | ∃ X : Finset (Fin 5), simple_graph_is_star_like ((SimpleGraph.pathGraph 5).induce (Xᶜ : Set (Fin 5))) ∧ X.card = k} := ⟨{0}, dominating_average_stability_path_five_delete_endpoint, by simp⟩ apply le_antisymm (Nat.sInf_le hmem) apply le_csInf ⟨1,hmem⟩ rintro k ⟨X,hX,rfl⟩ by_contra hbad have hxzero : X.card = 0 := by omega have hx : X = ∅ := Finset.card_eq_zero.mp hxzero subst X have hempty : ¬ simple_graph_is_star_like ((SimpleGraph.pathGraph 5).induce ((∅ : 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 exact hempty hX