AFTD Auto-Formalizing Theoretical Domains

dominating_average_stability_path_five_not_star

theoremverified

The five-vertex path is not star-like.

Statement

theorem dominating_average_stability_path_five_not_star :
    letI := dominating_average_stability_path_five_decidable
    ¬ simple_graph_is_star_like (SimpleGraph.pathGraph 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

The proof, explained

A graph is defined to be star-like if every vertex is either a leaf (degree 1) or has between 1 and 2 leaf neighbors. In the path graph on five vertices, the central vertex has degree 2 and both of its neighbors also have degree 2, so it has zero leaf neighbors, violating the star-like condition. The proof unfolds the definitions into explicit finite-set computations and disproves the property by direct kernel evaluation.

  1. The star-like condition on the 5-vertex path is rewritten as an explicit finite-set condition over the vertices of Fin 5.

    By definition, a graph is star-like if every vertex either has degree 1 or has between 1 and 2 leaf neighbors (neighbors of degree 1). Unfolding the definitions `simple_graph_is_star_like` and `simple_graph_leaf_neighbor_count`, and rewriting degrees and neighbor finsets using `SimpleGraph.degree` and `SimpleGraph.neighborFinset_eq_filter`, expresses the property purely as a boolean condition on the adjacencies of the 5 vertices.

    lines 7–8

    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. The five-vertex path graph is not star-like. automation

    Because the vertex set `Fin 5` is finite and graph adjacency is decidable, the universal condition reduces to checking each vertex. The central vertex (index 2) has degree 2 and no leaf neighbors (its neighbors both have degree 2), violating the condition. Lean's kernel evaluates the full finite boolean statement to false, proving the negation.

    line 9

      decide +kernel
SimpleGraph.degree
The degree of a vertex in a graph is the cardinality of its neighborhood.
SimpleGraph.neighborFinset_eq_filter
The neighborhood finset of a vertex in a finite graph equals the set 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_not_star :    letI := dominating_average_stability_path_five_decidable    ¬ simple_graph_is_star_like (SimpleGraph.pathGraph 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