AFTD Auto-Formalizing Theoretical Domains

dominating_average_stability_path_five_deletion

theoremverified

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
Used by 1

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.

  1. 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.

    lines 7–9

      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
  2. 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.

    lines 10–13

    uses dominating_average_stability_path_five_delete_endpoint

      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⟩
  3. 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.

    lines 14–15

    uses le_antisymm, Nat.sInf_le, le_csInf

      apply le_antisymm (Nat.sInf_le hmem)
      apply le_csInf ⟨1,hmem⟩
  4. 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 = ∅.

    lines 16–20

    uses Finset.card_eq_zero.mp

      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
  5. 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.

    lines 21–25

    uses SimpleGraph.degree, SimpleGraph.neighborFinset_eq_filter

      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
  6. 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.

    line 26

      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

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

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
See it in the graphDiscuss this resultChallenge it