simple_graph_local_avg_dominating_order_complete_four
In K₄, the dominating sets containing a fixed vertex have average size 5/2 = (4+1)/2.
Statement
theorem simple_graph_local_avg_dominating_order_complete_four :
simple_graph_local_avg_dominating_order (⊤ : SimpleGraph (Fin 4)) 0 = 5 / 2- Source
- Sanity check of the definitions of arXiv:2610.11446 (On the local average order of dominating sets). Sec. 1 gives avd_v(K_n) = (n+1)/2.
- Verified
- 09 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_local_avg_dominating_orderavd_v(G): the local average order of dominating sets containing v, i.e. the average size of the dominating sets of G that contain v.
- simple_graph_dominating_sets_containingD_v(G): the dominating sets of G that contain v, where S dominates G when every vertex is in S or adjacent to a vertex of S.
The proof, explained
The average size of a dominating set containing vertex 0 in the complete graph K₄ is computed directly from its definition as the total size of all such dominating sets divided by their count. In K₄, any set containing 0 is automatically dominating, yielding 2³ = 8 such sets whose sizes sum to 20. The proof determines both the count (8) and the sum of sizes (20) by exhaustive computational evaluation, and then simplifies the quotient 20 / 8 to 5 / 2.
There are 8 dominating sets in K₄ that contain vertex 0. automation
Unfolding the definition of dominating sets containing a given vertex leaves a decidable predicate over the power set of Fin 4. The `decide` tactic checks every subset of the 4-element vertex set exhaustively to determine that exactly 8 subsets contain 0 and dominate the complete graph.
have h1 : (simple_graph_dominating_sets_containing (⊤ : SimpleGraph (Fin 4)) 0).card = 8 := by unfold simple_graph_dominating_sets_containing; decide
The sum of the cardinalities of the dominating sets in K₄ containing vertex 0 is 20. automation
Unfolding the definition leaves a finite sum of cardinalities over the dominating sets in Fin 4 containing 0, which `decide` computes directly by finite evaluation.
have h2 : ∑ S ∈ simple_graph_dominating_sets_containing (⊤ : SimpleGraph (Fin 4)) 0, S.card = 20 := by unfold simple_graph_dominating_sets_containing; decide
The local average dominating order at vertex 0 is 5/2.
Unfolding the definition of the local average dominating order expresses it as the sum of the sizes of dominating sets containing 0 divided by their count. Rewriting with `Nat.cast_sum` pulls the cast out of the summation, allowing substitution of the sum (20) and the count (8). The arithmetic tactic `norm_num` then simplifies the quotient 20 / 8 to 5 / 2.
uses
Nat.cast_sumunfold simple_graph_local_avg_dominating_order rw [← Nat.cast_sum, h1, h2]; norm_num
Nat.cast_sum- The cast into a ring or monoid of a finite sum of natural numbers equals the sum of the individual casts.
- Rather than proving combinatorially that every non-empty set in a complete graph is dominating, the proof verifies the count and sum by computational reflection (`decide`) over all subsets of Fin 4.
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.
theorem simple_graph_local_avg_dominating_order_complete_four : simple_graph_local_avg_dominating_order (⊤ : SimpleGraph (Fin 4)) 0 = 5 / 2 := by have h1 : (simple_graph_dominating_sets_containing (⊤ : SimpleGraph (Fin 4)) 0).card = 8 := by unfold simple_graph_dominating_sets_containing; decide have h2 : ∑ S ∈ simple_graph_dominating_sets_containing (⊤ : SimpleGraph (Fin 4)) 0, S.card = 20 := by unfold simple_graph_dominating_sets_containing; decide unfold simple_graph_local_avg_dominating_order rw [← Nat.cast_sum, h1, h2]; norm_num