simple_graph_local_avg_dominating_order_bot_three
In the edgeless graph on 3 vertices, the only dominating set is the whole vertex set, so avd_v = 3.
Statement
theorem simple_graph_local_avg_dominating_order_bot_three :
simple_graph_local_avg_dominating_order (⊥ : SimpleGraph (Fin 3)) 0 = 3- Source
- Sanity check of the definitions of arXiv:2610.11446 (On the local average order of dominating sets). Sec. 1 gives avd_v of the empty graph = n.
- 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 proof evaluates the local average dominating set order directly from its definition: the sum of the cardinalities of all dominating sets containing vertex 0 divided by the number of such dominating sets. In the edgeless graph on 3 vertices, an exhaustive check via `decide` establishes that the full vertex set is the only dominating set containing 0. Substituting this count (1) and sum of sizes (3) yields an average order of $3 / 1 = 3$.
There is exactly 1 dominating set containing vertex 0 in the edgeless graph on 3 vertices. automation
By definition, a dominating set in a simple graph must contain every vertex that is not adjacent to some vertex in the set. Since the edgeless graph $\bot$ has no edges, every vertex must belong to the dominating set, leaving the full vertex set as the sole dominating set. Unfolding the definition of dominating sets containing vertex 0, Lean's computational decider `decide` verifies this by evaluating the finite predicate over all subsets of $\mathrm{Fin}\;3$.
have h1 : (simple_graph_dominating_sets_containing (⊥ : SimpleGraph (Fin 3)) 0).card = 1 := by unfold simple_graph_dominating_sets_containing; decide
The sum of the cardinalities of all dominating sets containing vertex 0 is 3. automation
Because the full vertex set of $\mathrm{Fin}\;3$ (having cardinality 3) is the unique dominating set containing vertex 0, the sum of cardinalities over all such dominating sets evaluates to 3. Unfolding the definition, the tactic `decide` computes this finite sum directly.
have h2 : ∑ S ∈ simple_graph_dominating_sets_containing (⊥ : SimpleGraph (Fin 3)) 0, S.card = 3 := by unfold simple_graph_dominating_sets_containing; decide
The local average dominating order at vertex 0 is 3.
Unfolding the definition of `simple_graph_local_avg_dominating_order`, the local average order is defined as the rational division of the sum of the cardinalities of the dominating sets containing 0 by their count. Rewriting the sum of rational casts into the cast of the natural sum using `Nat.cast_sum` allows substitution of the values from $h_1$ and $h_2$, leaving the rational evaluation $3 / 1 = 3$, which is solved by `norm_num`.
uses
Nat.cast_sumunfold simple_graph_local_avg_dominating_order rw [← Nat.cast_sum, h1, h2]; norm_num
Nat.cast_sum- The coercion from the natural numbers into an additive structure with one preserves finite sums: the sum of coerced terms equals the coercion of the sum.
- The facts that the edgeless graph on 3 vertices has only one dominating set containing vertex 0 and that the sum of its sizes is 3 are verified by exhaustive computation via `decide` over all subsets of `Fin 3`, rather than by general graph-theoretic lemmas.
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_bot_three : simple_graph_local_avg_dominating_order (⊥ : SimpleGraph (Fin 3)) 0 = 3 := by have h1 : (simple_graph_dominating_sets_containing (⊥ : SimpleGraph (Fin 3)) 0).card = 1 := by unfold simple_graph_dominating_sets_containing; decide have h2 : ∑ S ∈ simple_graph_dominating_sets_containing (⊥ : SimpleGraph (Fin 3)) 0, S.card = 3 := by unfold simple_graph_dominating_sets_containing; decide unfold simple_graph_local_avg_dominating_order rw [← Nat.cast_sum, h1, h2]; norm_num