AFTD Auto-Formalizing Theoretical Domains

simple_graph_local_avg_dominating_order_bot_three

theoremverified

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

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

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

    lines 3–4

      have h1 : (simple_graph_dominating_sets_containing (⊥ : SimpleGraph (Fin 3)) 0).card = 1 := by
        unfold simple_graph_dominating_sets_containing; decide
  2. 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.

    lines 5–7

      have h2 : ∑ S ∈ simple_graph_dominating_sets_containing (⊥ : SimpleGraph (Fin 3)) 0,
          S.card = 3 := by
        unfold simple_graph_dominating_sets_containing; decide
  3. 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`.

    lines 8–9

    uses Nat.cast_sum

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

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

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