AFTD Auto-Formalizing Theoretical Domains

simple_graph_local_avg_dominating_order_complete_four

theoremverified

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

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.

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

    lines 3–4

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

    lines 5–7

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

    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 cast into a ring or monoid of a finite sum of natural numbers equals the sum of the individual casts.

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