AFTD Auto-Formalizing Theoretical Domains

simple_graph_local_avg_dominating_order_ge

theoremverifiedformalization

For every finite graph G of order n and every vertex v, the dominating sets containing v have average size at least (n+1)/2, with equality if and only if v is adjacent to all other vertices (deg v = n − 1).

Statement

theorem simple_graph_local_avg_dominating_order_ge {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) :
    ((Fintype.card V : ℚ) + 1) / 2 ≤ simple_graph_local_avg_dominating_order G v ∧
      (simple_graph_local_avg_dominating_order G v = ((Fintype.card V : ℚ) + 1) / 2 ↔
        G.degree v = Fintype.card V - 1)
Formalizes
arXiv:2610.11446 (On the local average order of dominating sets), Theorem 2.2.
Verified
09 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

The theorem is proved by rephrasing dominating sets containing v in terms of their complements in X = V \ {v}. The family of complements I = {Sᶜ | S ∈ D} forms a nonempty down-closed family of subsets of X, so a general bound on down-closed families (finset_down_closed_family_avg_card_le) implies its average size is at most |X| / 2 = (n - 1) / 2, with equality if and only if I = 𝒫(X). Converting back from complements expresses the average size of D as n - avg(I), immediately yielding avg(D) ≥ (n + 1) / 2, with equality precisely when {v} is a dominating set, which occurs if and only if deg(v) = n - 1.

  1. Define the family D of dominating sets containing v, the order n = |V|, the universe X = V \ {v}, and the family of complements I = {Sᶜ | S ∈ D}, and unfold the membership condition for D.

    We work in classical logic. We name the family of dominating sets containing v as D, the total number of vertices as n, the set of all other vertices as X = V \ {v}, and the family of complements of sets in D as I. We then unfold the definition of dominating sets containing v to characterize membership in D: a set S ⊆ V belongs to D if and only if v ∈ S and every vertex w ∈ V is either in S or adjacent to some vertex in S.

    lines 6–12

      classical
      set D := simple_graph_dominating_sets_containing G v with hD
      set n := Fintype.card V with hn
      set X : Finset V := Finset.univ.erase v with hX
      set I := D.image (fun S => Sᶜ) with hI
      have memD : ∀ S, S ∈ D ↔ v ∈ S ∧ ∀ w, w ∈ S ∨ ∃ u ∈ S, G.Adj u w := by
        intro S; rw [hD]; unfold simple_graph_dominating_sets_containing; simp
  2. Complementation is injective on D, and both D and I are nonempty.

    Complementation is globally injective by compl_injective, hence injective on D. The full vertex set V is a dominating set containing v by Finset.mem_univ, so D is nonempty. Since I is the image of D under complementation, I is also nonempty.

    lines 13–15

    uses compl_injective, Finset.mem_univ

      have hcompl_inj : Set.InjOn (fun S : Finset V => Sᶜ) ↑D := fun S _ T _ h => compl_injective h
      have hDne : D.Nonempty := ⟨Finset.univ, (memD _).2 ⟨Finset.mem_univ v, fun w => Or.inl (Finset.mem_univ w)⟩⟩
      have hIne : I.Nonempty := hDne.image _
  3. Every set in I is a subset of X.

    Let T ∈ I, so T = Sᶜ for some S ∈ D. By definition of D, v ∈ S. Therefore, v ∉ Sᶜ = T. Since X = V \ {v}, any element w ∈ T satisfies w ≠ v and w ∈ V, which by Finset.mem_erase means w ∈ X, showing T ⊆ X.

    lines 16–23

    uses Finset.mem_erase

      have hIsub : ∀ T ∈ I, T ⊆ X := by
        intro T hT
        obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT
        intro w hw
        rw [hX, Finset.mem_erase]
        refine ⟨?_, Finset.mem_univ w⟩
        rintro rfl
        exact (Finset.mem_compl.1 hw) ((memD S).1 hS).1
  4. The family I is down-closed (an ideal): any subset of a set in I also belongs to I.

    Let T ∈ I and U ⊆ T. Write T = Sᶜ with S ∈ D. Since U ⊆ Sᶜ, contraposition yields S ⊆ Uᶜ via Finset.mem_compl. Because S contains v, its superset Uᶜ also contains v. Furthermore, since S is a dominating set, any vertex w ∈ V is dominated by some vertex in S, which also lies in Uᶜ. Hence Uᶜ ∈ D, and by compl_compl, U = (Uᶜ)ᶜ ∈ I.

    lines 24–35

    uses Finset.mem_compl, compl_compl

      have hIdown : ∀ T ∈ I, ∀ U ⊆ T, U ∈ I := by
        intro T hT U hU
        obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT
        have hSU : S ⊆ Uᶜ := by
          intro w hw
          rw [Finset.mem_compl]
          intro hwU
          exact (Finset.mem_compl.1 (hU hwU)) hw
        refine Finset.mem_image.2 ⟨Uᶜ, (memD _).2 ⟨hSU ((memD S).1 hS).1, fun w => ?_⟩, compl_compl U⟩
        rcases ((memD S).1 hS).2 w with h | ⟨u, hu, hadj⟩
        · exact Or.inl (hSU h)
        · exact Or.inr ⟨u, hSU hu, hadj⟩
  5. Compute |I| = |D|, ∑_{T ∈ I} |T| = ∑_{S ∈ D} (n - |S|), and |X| = n - 1 with n ≥ 1 and |D| > 0.

    Because complementation is injective on D, Finset.card_image_of_injOn gives |I| = |D|, and Finset.sum_image with Finset.sum_congr rewrites the sum of cardinalities over I as the sum of |Sᶜ| over S ∈ D. By Finset.card_compl, Nat.cast_sub, and Finset.card_le_univ, |Sᶜ| = n - |S|. Since X is obtained by erasing v from V, Finset.card_erase_of_mem gives |X| = n - 1. The vertex v witnesses n ≥ 1, and nonemptiness of D gives |D| > 0.

    lines 36–43

    uses Finset.card_image_of_injOn, Finset.sum_image, Finset.sum_congr, Finset.card_compl, Nat.cast_sub, Finset.card_le_univ, Finset.card_erase_of_mem

      have hcardI : I.card = D.card := Finset.card_image_of_injOn hcompl_inj
      have hsumI : ∑ T ∈ I, (T.card : ℚ) = ∑ S ∈ D, ((n : ℚ) - S.card) := by
        rw [hI, Finset.sum_image hcompl_inj]
        refine Finset.sum_congr rfl fun S _ => ?_
        rw [Finset.card_compl, Nat.cast_sub (Finset.card_le_univ S)]
      have hXcard : X.card = n - 1 := by rw [hX, Finset.card_erase_of_mem (Finset.mem_univ v)]; rfl
      have hn1 : 1 ≤ n := Fintype.card_pos_iff.2 ⟨v⟩
      have hDpos : (0 : ℚ) < D.card := by exact_mod_cast hDne.card_pos
  6. Apply the down-closed family inequality to I ⊆ 𝒫(X), expressing it as an upper bound on n - avg(D).

    Since I is a nonempty down-closed family of subsets of X, finset_down_closed_family_avg_card_le gives that the average size of sets in I is at most |X| / 2, with equality if and only if I = 𝒫(X). Substituting |I| = |D|, |X| = n - 1, and ∑_{T ∈ I} |T| = |D| * n - ∑_{S ∈ D} |S| using Finset.sum_sub_distrib, Finset.sum_const, and nsmul_eq_mul, the average size of sets in I simplifies via field arithmetic to n - avg(D). Thus, n - avg(D) ≤ (n - 1) / 2, with equality if and only if I = 𝒫(X), using Nat.cast_one.

    lines 44–52

    uses finset_down_closed_family_avg_card_le, Finset.sum_sub_distrib, Finset.sum_const, nsmul_eq_mul, Nat.cast_one

      have key := finset_down_closed_family_avg_card_le X I hIne hIsub hIdown
      rw [hsumI, hcardI, hXcard, Nat.cast_sub hn1, Finset.sum_sub_distrib, Finset.sum_const,
        nsmul_eq_mul] at key
      have havd : simple_graph_local_avg_dominating_order G v = (∑ S ∈ D, (S.card : ℚ)) / D.card := rfl
      have hsplit : ((D.card : ℚ) * n - ∑ S ∈ D, (S.card : ℚ)) / D.card =
          n - (∑ S ∈ D, (S.card : ℚ)) / D.card := by
        field_simp
      rw [hsplit, Nat.cast_one] at key
      obtain ⟨k1, k2⟩ := key
  7. The average dominating order satisfies avg(D) ≥ (n + 1) / 2. automation

    We split the conjunction into the inequality and the equivalence. From the bound n - avg(D) ≤ (n - 1) / 2, linear arithmetic over ℚ deduces avg(D) ≥ n - (n - 1) / 2 = (n + 1) / 2.

    lines 53–54

      refine ⟨?_, ?_⟩
      · rw [havd]; push_cast at k1 ⊢; linarith
  8. Equality avg(D) = (n + 1) / 2 holds if and only if I = 𝒫(X). automation

    Linear arithmetic shows that avg(D) = (n + 1) / 2 is equivalent to n - avg(D) = (n - 1) / 2. By the equality condition from the down-closed family bound, this occurs if and only if I = 𝒫(X).

    lines 55–59

      · rw [havd]
        have e1 : (∑ S ∈ D, (S.card : ℚ)) / D.card = ((n : ℚ) + 1) / 2 ↔
            (n : ℚ) - (∑ S ∈ D, (S.card : ℚ)) / D.card = ((n : ℚ) - 1) / 2 := by
          constructor <;> intro h <;> linarith
        rw [e1, k2]
  9. The degree of v is n - 1 if and only if v is adjacent to every vertex w ≠ v.

    The degree of v equals the cardinality of its neighbor finset N(v). Since G has no self-loops, N(v) ⊆ X = V \ {v}. If deg(v) = n - 1 = |X|, then by Finset.eq_of_subset_of_card_le, N(v) = X, so every w ≠ v is adjacent to v. Conversely, if v is adjacent to every w ≠ v, then X ⊆ N(v), so by Finset.Subset.antisymm, N(v) = X, which has size n - 1.

    lines 60–80

    uses Finset.eq_of_subset_of_card_le, Finset.Subset.antisymm

        -- the complements fill the power set iff `v` is adjacent to every other vertex
        have hdeg : G.degree v = n - 1 ↔ ∀ w, w ≠ v → G.Adj v w := by
          rw [← G.card_neighborFinset_eq_degree]
          have hsubN : G.neighborFinset v ⊆ X := by
            intro w hw
            rw [hX, Finset.mem_erase]
            exact ⟨(G.ne_of_adj ((G.mem_neighborFinset v w).1 hw)).symm, Finset.mem_univ w⟩
          constructor
          · intro h w hw
            have heq : G.neighborFinset v = X :=
              Finset.eq_of_subset_of_card_le hsubN (by rw [hXcard, h])
            have : w ∈ X := by rw [hX, Finset.mem_erase]; exact ⟨hw, Finset.mem_univ w⟩
            rw [← heq, G.mem_neighborFinset] at this
            exact this
          · intro h
            have heq : G.neighborFinset v = X := by
              refine Finset.Subset.antisymm hsubN fun w hw => ?_
              rw [hX, Finset.mem_erase] at hw
              rw [G.mem_neighborFinset]; exact h w hw.1
            rw [heq, hXcard]
        rw [hdeg]
  10. The complement family I equals 𝒫(X) if and only if v is adjacent to every vertex w ≠ v.

    We prove both directions of I = 𝒫(X) ↔ ∀ w ≠ v, G.Adj v w. First, if I = 𝒫(X), then X ∈ I by Finset.mem_powerset_self. Hence X = Sᶜ for some dominating set S ∈ D, which by compl_compl means S = Xᶜ = {v}. Since {v} dominates every vertex w, if w ≠ v it cannot be in {v}, so by Finset.mem_singleton it must be adjacent to the unique vertex in {v}, namely v. Conversely, suppose v is adjacent to all w ≠ v. Since I ⊆ 𝒫(X) is known, it suffices to show 𝒫(X) ⊆ I. Given T ∈ 𝒫(X), T ⊆ X by Finset.mem_powerset. Since v ∉ X, v ∉ T, so v ∈ Tᶜ by Finset.mem_compl. Any vertex w is either v ∈ Tᶜ, or w ≠ v, in which case w is adjacent to v ∈ Tᶜ. Thus Tᶜ ∈ D, and by compl_compl, T = (Tᶜ)ᶜ ∈ I. By Finset.Subset.antisymm, I = 𝒫(X).

    lines 81–102

    uses Finset.mem_powerset_self, compl_compl, Finset.mem_singleton, Finset.Subset.antisymm, Finset.mem_powerset, Finset.mem_compl

        constructor
        · intro hIX w hw
          have hXI : X ∈ I := by rw [hIX]; exact Finset.mem_powerset_self X
          obtain ⟨S, hS, hSX⟩ := Finset.mem_image.1 hXI
          have hSv : S = {v} := by
            rw [← compl_compl S, hSX, hX]
            ext u; simp
          rcases ((memD S).1 hS).2 w with h | ⟨u, hu, hadj⟩
          · rw [hSv, Finset.mem_singleton] at h; exact absurd h hw
          · rw [hSv, Finset.mem_singleton] at hu; rw [← hu]; exact hadj
        · intro hall
          refine Finset.Subset.antisymm (fun T hT => Finset.mem_powerset.2 (hIsub T hT)) fun T hT => ?_
          rw [Finset.mem_powerset] at hT
          have hvT : v ∈ Tᶜ := by
            rw [Finset.mem_compl]; intro h
            have := hT h
            rw [hX, Finset.mem_erase] at this
            exact this.1 rfl
          refine Finset.mem_image.2 ⟨Tᶜ, (memD _).2 ⟨hvT, fun w => ?_⟩, compl_compl T⟩
          by_cases hw : w = v
          · exact Or.inl (hw ▸ hvT)
          · exact Or.inr ⟨v, hvT, hall w hw⟩
compl_injective
The complement operation on a boolean algebra is injective: if Aᶜ = Bᶜ, then A = B.
Finset.card_image_of_injOn
The image of a finite set under a map injective on that set has the same cardinality as the original set.
Finset.sum_image
Summing a function over the image of a finite set under an injective map equals summing the composite function over the original set.
Finset.sum_congr
Two sums over finite sets are equal if their index sets are equal and their summands agree on every element.
Finset.card_compl
The cardinality of the complement of a subset s is the total number of elements minus the cardinality of s (|sᶜ| = |V| - |s|).
Nat.cast_sub
The coercion of a difference of natural numbers n - m to an additive group with one equals the difference of coercions ↑n - ↑m, provided m ≤ n.
Finset.card_le_univ
The cardinality of any subset of a finite type is at most the total number of elements in the type.
Finset.card_erase_of_mem
Removing an element from a finite set decreases its cardinality by 1, provided the element belongs to the set.
finset_down_closed_family_avg_card_le
For any nonempty down-closed family I of subsets of a finite set X, the average cardinality of sets in I is at most |X| / 2, with equality if and only if I is the full power set of X.
Finset.sum_sub_distrib
A finite sum of differences equals the difference of the finite sums (∑ (f - g) = ∑ f - ∑ g).
Finset.sum_const
Summing a constant value over a finite set equals the cardinality of the set scalar-multiplied by the constant.
nsmul_eq_mul
Scalar multiplication of an element by a natural number n equals multiplication by the coercion of n (n • a = ↑n * a).
Nat.cast_one
The coercion of the natural number 1 into an additive monoid with one equals 1.
Finset.eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s| for finite sets, then s = t.
Finset.Subset.antisymm
Two finite sets are equal if each is a subset of the other.
Finset.mem_powerset_self
Every finite set belongs to its own power set (s ∈ 𝒫(s)).
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
compl_compl
The double complement of a set is the set itself ((xᶜ)ᶜ = x).
Finset.mem_compl
An element belongs to the complement sᶜ of a finite set if and only if it does not belong to s.
Finset.mem_erase
An element belongs to s.erase b if and only if it is not equal to b and belongs to s.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Finset.mem_powerset
A finite set s belongs to the power set 𝒫(t) if and only if s ⊆ t.

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_ge {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) :    ((Fintype.card V : ℚ) + 1) / 2 ≤ simple_graph_local_avg_dominating_order G v ∧      (simple_graph_local_avg_dominating_order G v = ((Fintype.card V : ℚ) + 1) / 2 ↔        G.degree v = Fintype.card V - 1) := by  classical  set D := simple_graph_dominating_sets_containing G v with hD  set n := Fintype.card V with hn  set X : Finset V := Finset.univ.erase v with hX  set I := D.image (fun S => Sᶜ) with hI  have memD : ∀ S, S ∈ D ↔ v ∈ S ∧ ∀ w, w ∈ S ∨ ∃ u ∈ S, G.Adj u w := by    intro S; rw [hD]; unfold simple_graph_dominating_sets_containing; simp  have hcompl_inj : Set.InjOn (fun S : Finset V => Sᶜ) ↑D := fun S _ T _ h => compl_injective h  have hDne : D.Nonempty := ⟨Finset.univ, (memD _).2 ⟨Finset.mem_univ v, fun w => Or.inl (Finset.mem_univ w)⟩⟩  have hIne : I.Nonempty := hDne.image _  have hIsub : ∀ T ∈ I, T ⊆ X := by    intro T hT    obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT    intro w hw    rw [hX, Finset.mem_erase]    refine ⟨?_, Finset.mem_univ w⟩    rintro rfl    exact (Finset.mem_compl.1 hw) ((memD S).1 hS).1  have hIdown : ∀ T ∈ I, ∀ U ⊆ T, U ∈ I := by    intro T hT U hU    obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT    have hSU : S ⊆ Uᶜ := by      intro w hw      rw [Finset.mem_compl]      intro hwU      exact (Finset.mem_compl.1 (hU hwU)) hw    refine Finset.mem_image.2 ⟨Uᶜ, (memD _).2 ⟨hSU ((memD S).1 hS).1, fun w => ?_⟩, compl_compl U⟩    rcases ((memD S).1 hS).2 w with h | ⟨u, hu, hadj⟩    · exact Or.inl (hSU h)    · exact Or.inr ⟨u, hSU hu, hadj⟩  have hcardI : I.card = D.card := Finset.card_image_of_injOn hcompl_inj  have hsumI : ∑ T ∈ I, (T.card : ℚ) = ∑ S ∈ D, ((n : ℚ) - S.card) := by    rw [hI, Finset.sum_image hcompl_inj]    refine Finset.sum_congr rfl fun S _ => ?_    rw [Finset.card_compl, Nat.cast_sub (Finset.card_le_univ S)]  have hXcard : X.card = n - 1 := by rw [hX, Finset.card_erase_of_mem (Finset.mem_univ v)]; rfl  have hn1 : 1 ≤ n := Fintype.card_pos_iff.2 ⟨v⟩  have hDpos : (0 : ℚ) < D.card := by exact_mod_cast hDne.card_pos  have key := finset_down_closed_family_avg_card_le X I hIne hIsub hIdown  rw [hsumI, hcardI, hXcard, Nat.cast_sub hn1, Finset.sum_sub_distrib, Finset.sum_const,    nsmul_eq_mul] at key  have havd : simple_graph_local_avg_dominating_order G v = (∑ S ∈ D, (S.card : ℚ)) / D.card := rfl  have hsplit : ((D.card : ℚ) * n - ∑ S ∈ D, (S.card : ℚ)) / D.card =      n - (∑ S ∈ D, (S.card : ℚ)) / D.card := by    field_simp  rw [hsplit, Nat.cast_one] at key  obtain ⟨k1, k2⟩ := key  refine ⟨?_, ?_⟩  · rw [havd]; push_cast at k1 ⊢; linarith  · rw [havd]    have e1 : (∑ S ∈ D, (S.card : ℚ)) / D.card = ((n : ℚ) + 1) / 2 ↔        (n : ℚ) - (∑ S ∈ D, (S.card : ℚ)) / D.card = ((n : ℚ) - 1) / 2 := by      constructor <;> intro h <;> linarith    rw [e1, k2]    -- the complements fill the power set iff `v` is adjacent to every other vertex    have hdeg : G.degree v = n - 1 ↔ ∀ w, w ≠ v → G.Adj v w := by      rw [← G.card_neighborFinset_eq_degree]      have hsubN : G.neighborFinset v ⊆ X := by        intro w hw        rw [hX, Finset.mem_erase]        exact ⟨(G.ne_of_adj ((G.mem_neighborFinset v w).1 hw)).symm, Finset.mem_univ w⟩      constructor      · intro h w hw        have heq : G.neighborFinset v = X :=          Finset.eq_of_subset_of_card_le hsubN (by rw [hXcard, h])        have : w ∈ X := by rw [hX, Finset.mem_erase]; exact ⟨hw, Finset.mem_univ w⟩        rw [← heq, G.mem_neighborFinset] at this        exact this      · intro h        have heq : G.neighborFinset v = X := by          refine Finset.Subset.antisymm hsubN fun w hw => ?_          rw [hX, Finset.mem_erase] at hw          rw [G.mem_neighborFinset]; exact h w hw.1        rw [heq, hXcard]    rw [hdeg]    constructor    · intro hIX w hw      have hXI : X ∈ I := by rw [hIX]; exact Finset.mem_powerset_self X      obtain ⟨S, hS, hSX⟩ := Finset.mem_image.1 hXI      have hSv : S = {v} := by        rw [← compl_compl S, hSX, hX]        ext u; simp      rcases ((memD S).1 hS).2 w with h | ⟨u, hu, hadj⟩      · rw [hSv, Finset.mem_singleton] at h; exact absurd h hw      · rw [hSv, Finset.mem_singleton] at hu; rw [← hu]; exact hadj    · intro hall      refine Finset.Subset.antisymm (fun T hT => Finset.mem_powerset.2 (hIsub T hT)) fun T hT => ?_      rw [Finset.mem_powerset] at hT      have hvT : v ∈ Tᶜ := by        rw [Finset.mem_compl]; intro h        have := hT h        rw [hX, Finset.mem_erase] at this        exact this.1 rfl      refine Finset.mem_image.2 ⟨Tᶜ, (memD _).2 ⟨hvT, fun w => ?_⟩, compl_compl T⟩      by_cases hw : w = v      · exact Or.inl (hw ▸ hvT)      · exact Or.inr ⟨v, hvT, hall w hw⟩
See it in the graphDiscuss this resultChallenge it