AFTD Auto-Formalizing Theoretical Domains

dominating_average_stability_path_five_no_isolated

theoremverified

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

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`).

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

    line 7

    uses SimpleGraph.degree, SimpleGraph.neighborFinset_eq_filter

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

    line 8

      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.

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