simple_graph_avg_dominating_order_complete_two
The global average order of dominating sets of K2 is 4/3 (the three dominating sets {0}, {1}, {0,1} have sizes 1, 1, 2). Note this is exactly 2n/3 at n = 2, i.e. the equality case of the Beaton--Cameron bound, and it is smaller than the local value avd_v(K2) = 3/2 banked in simple_graph_local_avg_dominating_order_stem_le_of_card_two.
Statement
theorem simple_graph_avg_dominating_order_complete_two :
simple_graph_avg_dominating_order (⊤ : SimpleGraph (Fin 2)) = 4 / 3- Source
- step towards simple_graph_local_avg_dominating_order_stem_le
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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.
The proof, explained
The global average order of dominating sets of the complete graph $K_2$ is computed directly by exhaustive enumeration. Since any non-empty subset of the vertices dominates, there are exactly three dominating sets: $\{0\}$, $\{1\}$, and $\{0, 1\}$. Summing their cardinalities gives $1 + 1 + 2 = 4$, and dividing by their count of $3$ yields the average order $4/3$.
The dominating sets of $K_2$ are $\{0\}$, $\{1\}$, and $\{0, 1\}$, and the average dominating set order is their average cardinality.
In the complete graph on two vertices $K_2$, every non-empty set of vertices is dominating. A finite decision procedure (`decide`) exhaustively checks all subsets of $\mathrm{Fin}\,2$ to establish that the dominating sets are precisely $\{0\}$, $\{1\}$, and $\{0, 1\}$. Rewriting with the definition of `simple_graph_avg_dominating_order` and this list of dominating sets expresses the average order as the sum of their sizes divided by the number of dominating sets.
uses
simple_graph_avg_dominating_orderhave hs : simple_graph_dominating_sets (⊤ : SimpleGraph (Fin 2)) = {{0},{1},{0,1}} := by decide rw [simple_graph_avg_dominating_order, hs]
The sum of the cardinalities of the dominating sets of $K_2$ is $4$, both in $\mathbb{N}$ and in $\mathbb{Q}$.
Computing the sizes of the three dominating sets gives $1 + 1 + 2 = 4$ in $\mathbb{N}$ via finite evaluation (`decide`). Rewriting with `Nat.cast_sum` moves the cast to $\mathbb{Q}$ outside the finite sum, allowing the natural sum to be replaced by $4$, which `norm_num` simplifies to the rational number $4$.
uses
Nat.cast_sumhave hsum : (∑ S ∈ ({{0},{1},{0,1}} : Finset (Finset (Fin 2))), S.card) = 4 := by decide have h1 : (∑ S ∈ ({{0},{1},{0,1}} : Finset (Finset (Fin 2))), (S.card : ℚ)) = 4 := by rw [← Nat.cast_sum, hsum] norm_num
The complete graph $K_2$ has exactly $3$ dominating sets.
The cardinality of the three-element set of dominating sets $\{\{0\}, \{1\}, \{0, 1\}\}$ is computed to be $3$ by `decide`.
have h2 : ({{0},{1},{0,1}} : Finset (Finset (Fin 2))).card = 3 := by decide
The average dominating set order of $K_2$ is $4/3$.
Substituting the numerator ($4$) and the denominator ($3$) into the expression for the average dominating set order reduces the goal to $4 / 3 = 4 / 3$, which is closed by numerical normalization (`norm_num`).
rw [h1, h2] norm_num
simple_graph_avg_dominating_order- The definition of the average order of dominating sets on a graph, defined as the sum of the cardinalities of all dominating sets divided by the total number of dominating sets.
Nat.cast_sum- The canonical cast from the natural numbers to an additive monoid with one distributes across finite sums: `↑(∑ x ∈ s, f x) = ∑ x ∈ s, ↑(f x)`.
- The conversion from a sum of natural numbers to a sum of rational numbers (via `Nat.cast_sum`) is a formal type-casting step that has no counterpart on paper.
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.
/-- Sanity value of the global average: on K2 the three dominating sets have sizes 1,1,2, so avd(K2) = 4/3 = 2·2/3. -/theorem simple_graph_avg_dominating_order_complete_two : simple_graph_avg_dominating_order (⊤ : SimpleGraph (Fin 2)) = 4 / 3 := by have hs : simple_graph_dominating_sets (⊤ : SimpleGraph (Fin 2)) = {{0},{1},{0,1}} := by decide rw [simple_graph_avg_dominating_order, hs] have hsum : (∑ S ∈ ({{0},{1},{0,1}} : Finset (Finset (Fin 2))), S.card) = 4 := by decide have h1 : (∑ S ∈ ({{0},{1},{0,1}} : Finset (Finset (Fin 2))), (S.card : ℚ)) = 4 := by rw [← Nat.cast_sum, hsum] norm_num have h2 : ({{0},{1},{0,1}} : Finset (Finset (Fin 2))).card = 3 := by decide rw [h1, h2] norm_num