AFTD Auto-Formalizing Theoretical Domains

dominating_average_stability_path_five_mean

theoremverified

The five-vertex path has average dominating-set size55/17.

Statement

theorem dominating_average_stability_path_five_mean :
    letI := dominating_average_stability_path_five_decidable
    simple_graph_avg_dominating_order (SimpleGraph.pathGraph 5) = 55/17
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

The theorem is proved by finite exhaustive computation. Unfolding the definitions expresses the average dominating set size of the path graph $P_5$ as the sum of cardinalities of all dominating sets divided by the total number of dominating sets. Because $P_5$ has only 5 vertices, Lean's kernel directly tests all 32 candidate subsets via `decide +kernel`, finding 17 dominating sets with total cardinality 55 and confirming the ratio $55/17$.

  1. The goal reduces to showing that the sum of sizes of dominating sets in the path graph $P_5$ divided by the number of dominating sets equals $55/17$.

    Unfold the definition of the average dominating set order, `simple_graph_avg_dominating_order`, and of the collection of dominating sets, `simple_graph_dominating_sets`. In this graph, a dominating set is a subset $S \subseteq \mathrm{Fin}\;5$ such that every vertex $w$ is either in $S$ or adjacent to some vertex in $S$.

    line 7

      unfold simple_graph_avg_dominating_order simple_graph_dominating_sets
  2. The equality holds: the average dominating set size of the 5-vertex path graph is $55/17$. automation

    Since $P_5$ has only 5 vertices, there are $2^5 = 32$ subsets to check. Lean's kernel enumerates these subsets, finds that exactly 17 of them are dominating sets and that their sizes sum to 55, confirming the fraction $55/17$.

    line 8

      decide +kernel

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_mean :    letI := dominating_average_stability_path_five_decidable    simple_graph_avg_dominating_order (SimpleGraph.pathGraph 5) = 55/17 := by  unfold simple_graph_avg_dominating_order simple_graph_dominating_sets  decide +kernel
See it in the graphDiscuss this resultChallenge it