dominating_average_stability_path_five_mean
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
- simple_graph_avg_dominating_orderavd(G): the global average order of dominating sets of G, i.e. the average size of all dominating sets of G. This is the quantity of…
- simple_graph_dominating_setsD(G): the dominating sets of G, i.e. the finite vertex sets S such that every vertex of G lies in S or is adjacent to a vertex of S.
- dominating_average_stability_path_five_decidableAn explicit computable adjacency decision for the five-vertex path.
- Used by 1
- dominating_average_stability_constant_lower_boundAny multiplicative stability coefficient valid on the five-vertex path is at least51/5. This is a necessary constant, not the universal…
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$.
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$.
unfold simple_graph_avg_dominating_order simple_graph_dominating_setsThe 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$.
decide +kernel
- The entire calculation is performed by Lean's kernel via `decide +kernel`, which exhaustively tests all 32 vertex subsets of the 5-vertex path and verifies the rational arithmetic without intermediate user-level steps.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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