AFTD Auto-Formalizing Theoretical Domains

dominating_average_stability_path_five_delete_endpoint

theoremverified

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

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.

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

    lines 8–9

    uses SimpleGraph.degree, SimpleGraph.neighborFinset_eq_filter

      unfold simple_graph_is_star_like simple_graph_leaf_neighbor_count
      simp only [SimpleGraph.degree, SimpleGraph.neighborFinset_eq_filter]
  2. 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.

    line 10

      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.

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