AFTD Auto-Formalizing Theoretical Domains

dominating_average_stability_constant_lower_bound

theoremverified

Any multiplicative stability coefficient valid on the five-vertex path is at least51/5. This is a necessary constant, not the universal stability inequality.

Statement

theorem dominating_average_stability_constant_lower_bound (C : ℚ) :
    letI := dominating_average_stability_path_five_decidable
    (simple_graph_star_like_deletion_number (SimpleGraph.pathGraph 5) : ℚ) ≤
      C * (2 * (Fintype.card (Fin 5) : ℚ) / 3 -
        simple_graph_avg_dominating_order (SimpleGraph.pathGraph 5)) → 51/5 ≤ C
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

The proof, explained

The theorem establishes a necessary lower bound on the stability constant by evaluating the candidate inequality on a single counterexample graph: the 5-vertex path graph P₅. For this graph, the star-like deletion number is 1, the number of vertices is 5, and the average dominating set order is 55/17. Substituting these explicit quantities into the stability inequality reduces it to 1 ≤ C * (5/51), which immediately forces C ≥ 51/5.

  1. The stability condition on the 5-vertex path graph simplifies to the requirement that 1 ≤ C * (5 / 51).

    After providing the decidability of adjacency on the 5-vertex path graph, we rewrite the star-like deletion number of the path graph as 1 using dominating_average_stability_path_five_deletion and its average dominating set order as 55/17 using dominating_average_stability_path_five_mean. Numerical normalization then evaluates the vertex count as 5 and computes the rational expression 2 * 5 / 3 - 55 / 17 = 5 / 51.

    lines 9–12

    uses dominating_average_stability_path_five_deletion, dominating_average_stability_path_five_mean

      letI := dominating_average_stability_path_five_decidable
      rw [dominating_average_stability_path_five_deletion,
          dominating_average_stability_path_five_mean]
      norm_num
  2. The stability constant C satisfies 51/5 ≤ C.

    Assume the simplified hypothesis 1 ≤ C * (5 / 51). Multiplying both sides by 51/5 yields 51/5 ≤ C, which linear rational arithmetic confirms to complete the proof.

    lines 13–14

      intro h
      linarith
dominating_average_stability_path_five_deletion
The star-like deletion number of the 5-vertex path graph is 1.
dominating_average_stability_path_five_mean
The average cardinality of a dominating set in the 5-vertex path graph is 55/17.

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_constant_lower_bound (C : ℚ) :    letI := dominating_average_stability_path_five_decidable    (simple_graph_star_like_deletion_number (SimpleGraph.pathGraph 5) : ℚ) ≤      C * (2 * (Fintype.card (Fin 5) : ℚ) / 3 -        simple_graph_avg_dominating_order (SimpleGraph.pathGraph 5)) → 51/5 ≤ C := by  letI := dominating_average_stability_path_five_decidable  rw [dominating_average_stability_path_five_deletion,      dominating_average_stability_path_five_mean]  norm_num  intro h  linarith
See it in the graphDiscuss this resultChallenge it