simple_graph_local_avg_dominating_order_ge
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
- 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.
- finset_down_closed_family_avg_card_leA nonempty downward-closed family I of subsets of a finite set X has average set size at most |X|/2, with equality exactly when I is the…
- Used by 1
- simple_graph_local_avg_dominating_order_eq_four_mul_add_one_of_universalRigidity in the universal-vertex regime: if G has no isolated vertices, v is adjacent to every other vertex (deg v = n − 1), and avd_v(G)…
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.
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.
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
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.
uses
compl_injective,Finset.mem_univhave 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 _
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.
uses
Finset.mem_erasehave 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
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.
uses
Finset.mem_compl,compl_complhave 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⟩
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.
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_memhave 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
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.
uses
finset_down_closed_family_avg_card_le,Finset.sum_sub_distrib,Finset.sum_const,nsmul_eq_mul,Nat.cast_onehave 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
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.
refine ⟨?_, ?_⟩ · rw [havd]; push_cast at k1 ⊢; linarith
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).
· 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 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.
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]
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).
uses
Finset.mem_powerset_self,compl_compl,Finset.mem_singleton,Finset.Subset.antisymm,Finset.mem_powerset,Finset.mem_complconstructor · 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
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_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⟩