AFTD Auto-Formalizing Theoretical Domains

simple_graph_avg_dominating_order_complete_two

theoremverified

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

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

    lines 4–5

    uses simple_graph_avg_dominating_order

      have hs : simple_graph_dominating_sets (⊤ : SimpleGraph (Fin 2)) = {{0},{1},{0,1}} := by decide
      rw [simple_graph_avg_dominating_order, hs]
  2. 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$.

    lines 6–9

    uses Nat.cast_sum

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

    line 10

      have h2 : ({{0},{1},{0,1}} : Finset (Finset (Fin 2))).card = 3 := by decide
  4. 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`).

    lines 11–12

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

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

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