simple_graph_local_avg_dominating_order_le_of_no_isolated
If the finite graph G of order n has no isolated vertices, then for every vertex v the dominating sets containing v have average size at most (5n − 2 deg(v) + 1)/6 (hence at most (5n − 1)/6).
Statement
theorem simple_graph_local_avg_dominating_order_le_of_no_isolated {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hiso : ∀ w, 0 < G.degree w) (v : V) : simple_graph_local_avg_dominating_order G v ≤ (5 * (Fintype.card V : ℚ) - 2 * G.degree v + 1) / 6
- Formalizes
- arXiv:2610.11446 (On the local average order of dominating sets), Theorem 3.8, second statement (the first, the sum bound (n+1)/2 + ½ Σ_{u ∉ N[v]} (deg u + 1)/(2^{deg u + 1} − 1), is not stated here).
- 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.
- Used by 1
- simple_graph_local_avg_dominating_order_stem_le_of_card_le_two_mul_degreeIf G has no isolated vertices and |V| ≤ 2 deg(v), then avd_v(G) ≤ (4|V|+1)/6. This is the large-degree regime of the target's inequality,…
The proof, explained
The theorem bounds the average size of dominating sets containing a designated vertex v in a graph without isolated vertices. By decomposing dominating sets containing x into those where x is removable and those where x is critical, we obtain the identity 2 ∑ a(x) = n |D| + ∑ c(x). For x ≠ v, criticality requires the dominating set to meet the closed neighborhood of some vertex w ∉ N[v] in exactly {x}, and a 2-to-1 map shows that at most two-thirds of dominating sets meet N[w] in a single vertex. Combining these bounds yields 3 ∑ c(x) ≤ 3 |D| + 2 (n - 1 - deg(v)) |D|, from which the upper bound (5n - 2 deg(v) + 1)/6 follows immediately.
The family D of dominating sets containing v is nonempty, characterized by domination of every vertex, and closed under taking supersets.
We define D as the collection of dominating sets containing v and n as |V|. A set S is in D if and only if v ∈ S and every vertex w is in S or has a neighbor in S. If S ∈ D and S ⊆ T, then v ∈ T and every vertex dominated by S is also dominated by T, so T ∈ D. The universal set Finset.univ dominates every vertex and contains v, so D is nonempty.
uses
Finset.mem_univ,Finset.univ,Or.inl,Or.inrclassical set D := simple_graph_dominating_sets_containing G v with hD set n := Fintype.card V with hn 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 -- `D` is closed under supersets have hup : ∀ S ∈ D, ∀ T, S ⊆ T → T ∈ D := by intro S hS T hST rw [memD] at hS ⊢ refine ⟨hST hS.1, fun w => ?_⟩ rcases hS.2 w with h | ⟨u, hu, h⟩ · exact Or.inl (hST h) · exact Or.inr ⟨u, hST hu, h⟩ have hDne : D.Nonempty := ⟨Finset.univ, (memD _).2 ⟨Finset.mem_univ v, fun w => Or.inl (Finset.mem_univ w)⟩⟩
The set U of vertices not dominated by v alone has cardinality |U| = n - 1 - deg(v), and deg(v) ≤ n - 1.
For any w, N[w] denotes the closed neighborhood {w} ∪ N(w). The set U = (V \ {v}) \ N(v) consists of all vertices other than v that are not adjacent to v. Since the neighbor set N(v) has size deg(v) and is disjoint from {v}, subtracting its size from |V \ {v}| = n - 1 yields |U| = n - 1 - deg(v). Because N(v) ⊆ V \ {v}, we also have deg(v) ≤ n - 1, and V is nonempty since it contains v.
uses
Finset.card_erase_of_mem,Finset.card_le_card,Finset.card_sdiff_of_subset,Finset.mem_erase,Finset.mem_univ,Fintype.card_pos_iff,G.card_neighborFinset_eq_degree,G.mem_neighborFinset,G.ne_of_adj-- closed neighbourhoods and the vertices outside `N[v]` set N : V → Finset V := fun w => insert w (G.neighborFinset w) with hN set U : Finset V := (Finset.univ.erase v) \ G.neighborFinset v with hU have hUcard : U.card = n - 1 - G.degree v := by rw [hU, Finset.card_sdiff_of_subset, Finset.card_erase_of_mem (Finset.mem_univ v), G.card_neighborFinset_eq_degree] · rfl · intro w hw rw [Finset.mem_erase] exact ⟨(G.ne_of_adj ((G.mem_neighborFinset v w).1 hw)).symm, Finset.mem_univ w⟩ have hdegle : G.degree v ≤ n - 1 := by rw [← G.card_neighborFinset_eq_degree] have : G.neighborFinset v ⊆ Finset.univ.erase v := by intro w hw rw [Finset.mem_erase] exact ⟨(G.ne_of_adj ((G.mem_neighborFinset v w).1 hw)).symm, Finset.mem_univ w⟩ calc (G.neighborFinset v).card ≤ (Finset.univ.erase v).card := Finset.card_le_card this _ = n - 1 := by rw [Finset.card_erase_of_mem (Finset.mem_univ v)]; rfl have hn1 : 1 ≤ n := Fintype.card_pos_iff.2 ⟨v⟩
For each vertex x, the number a(x) of dominating sets containing x equals the number b(x) avoiding x plus the number c(x) in which x is critical: a(x) = b(x) + c(x).
We partition {S ∈ D : x ∈ S} into those where S \ {x} is still in D and those where S \ {x} ∉ D. The latter sets are precisely those where x is critical, of which there are c(x). The former sets are in bijection with dominating sets avoiding x via S ↦ S \ {x}, with inverse T ↦ T ∪ {x} (which remains in D because D is closed under supersets). Hence their size is b(x), giving a(x) = b(x) + c(x). Together with a(x) + b(x) = |D|, this is the key splitting identity.
uses
Finset.card_filter_add_card_filter_not,Finset.card_image_of_injOn,Finset.card_le_card,Finset.erase_insert,Finset.filter_filter,Finset.insert_erase,Finset.mem_insert_self,Finset.subset_insert,congrArg,le_antisymm-- counts: `a x` sets containing `x`, `b x` avoiding `x`, `c x` sets in which `x` is critical set a : V → ℕ := fun x => (D.filter (fun S => x ∈ S)).card with ha set b : V → ℕ := fun x => (D.filter (fun S => x ∉ S)).card with hb set c : V → ℕ := fun x => (D.filter (fun S => x ∈ S ∧ S.erase x ∉ D)).card with hc have hab : ∀ x, a x + b x = D.card := fun x => Finset.card_filter_add_card_filter_not _ have habc : ∀ x, a x = b x + c x := by intro x simp only [ha, hb, hc] have hsplit : (D.filter (fun S => x ∈ S)).card = ((D.filter (fun S => x ∈ S)).filter (fun S => S.erase x ∈ D)).card + ((D.filter (fun S => x ∈ S)).filter (fun S => ¬ S.erase x ∈ D)).card := (Finset.card_filter_add_card_filter_not _).symm rw [Finset.filter_filter, Finset.filter_filter] at hsplit rw [hsplit] congr 1 -- erasing `x` matches the sets with `x` removable with the sets avoiding `x` apply le_antisymm · have inj : Set.InjOn (fun S : Finset V => S.erase x) ↑(D.filter (fun S => x ∈ S ∧ S.erase x ∈ D)) := by intro S hS T hT h simp only [Finset.mem_coe, Finset.mem_filter] at hS hT rw [← Finset.insert_erase hS.2.1, ← Finset.insert_erase hT.2.1] exact congrArg (insert x) h rw [← Finset.card_image_of_injOn inj] apply Finset.card_le_card intro T hT obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT simp only [Finset.mem_filter] at hS ⊢ exact ⟨hS.2.2, by simp⟩ · have inj : Set.InjOn (fun S : Finset V => insert x S) ↑(D.filter (fun S => x ∉ S)) := by intro S hS T hT h simp only [Finset.mem_coe, Finset.mem_filter] at hS hT rw [← Finset.erase_insert hS.2, ← Finset.erase_insert hT.2] exact congrArg (fun W => Finset.erase W x) h rw [← Finset.card_image_of_injOn inj] apply Finset.card_le_card intro T hT obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT simp only [Finset.mem_filter] at hS ⊢ refine ⟨hup S hS.1 _ (Finset.subset_insert x S), Finset.mem_insert_self x S, ?_⟩ rw [Finset.erase_insert hS.2]; exact hS.1
The sum of the sizes of all dominating sets in D equals ∑_{x ∈ V} a(x).
Each set cardinality |S| can be expressed as the sum of indicator values ∑_{x ∈ V} [x ∈ S]. Interchanging the summation over S ∈ D and x ∈ V double counts the pairs (x, S) with x ∈ S, yielding ∑_{S ∈ D} |S| = ∑_{x ∈ V} a(x).
uses
Finset.card_filter,Finset.filter_mem_eq_inter,Finset.sum_comm,Finset.sum_congr,Finset.univ_interhave hsum : ∑ S ∈ D, S.card = ∑ x, a x := by have h : ∀ S ∈ D, S.card = ∑ x, if x ∈ S then 1 else 0 := by intro S _ rw [← Finset.card_filter, Finset.filter_mem_eq_inter, Finset.univ_inter] rw [Finset.sum_congr rfl h, Finset.sum_comm] refine Finset.sum_congr rfl fun x _ => ?_ simp only [ha]; rw [Finset.card_filter]
For x ≠ v, every dominating set in which x is critical meets N[w] in exactly {x} for some w ∈ U, so c(x) ≤ ∑_{w ∈ U} |E(w, x)|.
If x ≠ v and x is critical in S, then S \ {x} contains v but fails to dominate the whole graph. Some vertex w is not dominated by S \ {x}, so S \ {x} is disjoint from N[w]. Since S dominated w, x must dominate w, meaning S ∩ N[w] = {x}. Moreover, w cannot be v (since v ∈ S \ {x}) nor adjacent to v (since v would dominate w), which places w in U. By the union bound, c(x) ≤ ∑_{w ∈ U} |E(w, x)|.
uses
Finset.card_biUnion_le,Finset.card_le_card,Finset.mem_biUnion,Finset.mem_erase,Finset.mem_filter,Finset.mem_sdiff,Finset.mem_univ,G.mem_neighborFinset,le_trans-- `x ≠ v` critical in `S`: `S` meets some `N[w]`, `w ∉ N[v]`, exactly in `x` set E : V → V → Finset (Finset V) := fun w x => D.filter (fun S => S ∩ N w = {x}) with hE have hcrit : ∀ x, x ≠ v → c x ≤ ∑ w ∈ U, (E w x).card := by intro x hxv simp only [hc] refine le_trans (Finset.card_le_card ?_) Finset.card_biUnion_le intro S hS rw [Finset.mem_filter] at hS obtain ⟨hSD, hxS, hSx⟩ := hS have hvS : v ∈ S.erase x := Finset.mem_erase.2 ⟨hxv.symm, ((memD S).1 hSD).1⟩ rw [memD] at hSx push_neg at hSx obtain ⟨w, hwS, hwadj⟩ := hSx hvS have hNw : S ∩ N w = {x} := by ext y simp only [Finset.mem_inter, hN, Finset.mem_insert, G.mem_neighborFinset, Finset.mem_singleton] constructor · rintro ⟨hyS, hy⟩ by_contra hyx have hy' : y ∈ S.erase x := Finset.mem_erase.2 ⟨hyx, hyS⟩ rcases hy with rfl | hy · exact hwS hy' · exact hwadj y hy' hy.symm · intro hyx rw [hyx] refine ⟨hxS, ?_⟩ rcases ((memD S).1 hSD).2 w with h | ⟨u, hu, h⟩ · left by_contra hne exact hwS (Finset.mem_erase.2 ⟨fun h' => hne h'.symm, h⟩) · right by_cases hux : u = x · rw [← hux]; exact h.symm · exact absurd h (hwadj u (Finset.mem_erase.2 ⟨hux, hu⟩)) have hwU : w ∈ U := by rw [hU, Finset.mem_sdiff, Finset.mem_erase, G.mem_neighborFinset] refine ⟨⟨fun h => hwS (h ▸ hvS), Finset.mem_univ w⟩, fun h => hwadj v hvS h⟩ exact Finset.mem_biUnion.2 ⟨w, hwU, Finset.mem_filter.2 ⟨hSD, hNw⟩⟩
For every vertex w, at most two-thirds of the dominating sets in D meet N[w] in exactly one vertex: 3 |{S ∈ D : |S ∩ N[w]| = 1}| ≤ 2 |D|.
Since G has no isolated vertices, w has a neighbor w'. We partition D into sets meeting N[w] in 1 vertex ('single') and those meeting N[w] in a different number of vertices ('multi'). Define φ on 'single' by adding w' if w ∈ S, and adding w if w ∉ S. By superset closure, φ(S) ∈ D, and its intersection with N[w] has size at least 2, so φ(S) ∈ 'multi'. Each target set has at most two preimages (erasing w' or erasing w). Thus |single| ≤ 2 |multi|. Combining this with |single| + |multi| = |D| yields 3 |single| ≤ 2 |D|.
uses
Finset.card_eq_one,Finset.card_filter_add_card_filter_not,Finset.card_le_mul_card_image_of_maps_to,Finset.card_le_one,Finset.card_le_two,Finset.card_pos,Finset.erase_insert,Finset.mem_singleton_self,Finset.subset_insert,G.card_neighborFinset_eq_degree,G.mem_neighborFinset,G.ne_of_adj,if_neg,if_pos,le_trans-- at most two thirds of the sets meet `N[w]` in a single vertex have hthird : ∀ w, 3 * (D.filter (fun S => (S ∩ N w).card = 1)).card ≤ 2 * D.card := by intro w obtain ⟨w', hw'⟩ : ∃ w', G.Adj w w' := by have := hiso w rw [← G.card_neighborFinset_eq_degree, Finset.card_pos] at this obtain ⟨w', hw'⟩ := this exact ⟨w', (G.mem_neighborFinset w w').1 hw'⟩ have hww' : w ≠ w' := G.ne_of_adj hw' have hwN : w ∈ N w := by simp [hN] have hw'N : w' ∈ N w := by simp [hN, G.mem_neighborFinset, hw'] set single := D.filter (fun S => (S ∩ N w).card = 1) with hsingle set multi := D.filter (fun S => ¬ (S ∩ N w).card = 1) with hmulti have hsm : single.card + multi.card = D.card := Finset.card_filter_add_card_filter_not _ let φ : Finset V → Finset V := fun S => if w ∈ S then insert w' S else insert w S have hmaps : ∀ S ∈ single, φ S ∈ multi := by intro S hS rw [hsingle, Finset.mem_filter, Finset.card_eq_one] at hS obtain ⟨hSD, z, hz⟩ := hS rw [hmulti, Finset.mem_filter] by_cases hwS : w ∈ S · simp only [φ, if_pos hwS] refine ⟨hup S hSD _ (Finset.subset_insert _ _), fun h1 => ?_⟩ have hw_in : w ∈ insert w' S ∩ N w := Finset.mem_inter.2 ⟨Finset.mem_insert_of_mem hwS, hwN⟩ have hw'_in : w' ∈ insert w' S ∩ N w := Finset.mem_inter.2 ⟨Finset.mem_insert_self _ _, hw'N⟩ exact hww' (Finset.card_le_one.1 h1.le w hw_in w' hw'_in) · simp only [φ, if_neg hwS] refine ⟨hup S hSD _ (Finset.subset_insert _ _), fun h1 => ?_⟩ have hz_in : z ∈ S ∩ N w := by rw [hz]; exact Finset.mem_singleton_self z have hzw : z ≠ w := fun h => hwS (h ▸ (Finset.mem_inter.1 hz_in).1) have hw_in : w ∈ insert w S ∩ N w := Finset.mem_inter.2 ⟨Finset.mem_insert_self _ _, hwN⟩ have hz_in' : z ∈ insert w S ∩ N w := Finset.mem_inter.2 ⟨Finset.mem_insert_of_mem (Finset.mem_inter.1 hz_in).1, (Finset.mem_inter.1 hz_in).2⟩ exact hzw (Finset.card_le_one.1 h1.le z hz_in' w hw_in) have hfib : ∀ M, (single.filter (fun S => φ S = M)).card ≤ 2 := by intro M refine le_trans (Finset.card_le_card (t := {M.erase w', M.erase w}) ?_) Finset.card_le_two intro S hS rw [Finset.mem_filter, hsingle, Finset.mem_filter, Finset.card_eq_one] at hS obtain ⟨⟨_, z, hz⟩, hφ⟩ := hS rw [Finset.mem_insert, Finset.mem_singleton] by_cases hwS : w ∈ S · left simp only [φ, if_pos hwS] at hφ have hw'S : w' ∉ S := by intro h have h1 : w ∈ S ∩ N w := Finset.mem_inter.2 ⟨hwS, hwN⟩ have h2 : w' ∈ S ∩ N w := Finset.mem_inter.2 ⟨h, hw'N⟩ rw [hz, Finset.mem_singleton] at h1 h2 exact hww' (h1.trans h2.symm) rw [← hφ, Finset.erase_insert hw'S] · right simp only [φ, if_neg hwS] at hφ rw [← hφ, Finset.erase_insert hwS] have hle2 : single.card ≤ 2 * multi.card := Finset.card_le_mul_card_image_of_maps_to hmaps 2 (fun M _ => hfib M) omega
For each vertex w, the sets E(w, x) for x ≠ v are pairwise disjoint, so ∑_{x ≠ v} |E(w, x)| ≤ |{S ∈ D : |S ∩ N[w]| = 1}|.
If S ∈ E(w, x) ∩ E(w, y), then S ∩ N[w] is both {x} and {y}, so x = y by injectivity of singletons. Thus the sets E(w, x) are pairwise disjoint. Moreover, every S ∈ E(w, x) satisfies |S ∩ N[w]| = 1. The sum of the cardinalities of disjoint subsets is the cardinality of their union, which is bounded by the cardinality of the ambient family.
uses
Finset.card_biUnion,Finset.card_le_card,Finset.card_singleton,Finset.disjoint_left,Finset.mem_biUnion,Finset.mem_filter,Finset.singleton_injective,Function.onFunhave hEsum : ∀ w, ∑ x ∈ Finset.univ.erase v, (E w x).card ≤ (D.filter (fun S => (S ∩ N w).card = 1)).card := by intro w rw [← Finset.card_biUnion] · apply Finset.card_le_card intro S hS obtain ⟨x, -, hx⟩ := Finset.mem_biUnion.1 hS rw [hE, Finset.mem_filter] at hx rw [Finset.mem_filter, hx.2, Finset.card_singleton] exact ⟨hx.1, rfl⟩ · intro x _ y _ hxy rw [Function.onFun, Finset.disjoint_left] intro S hSx hSy rw [hE, Finset.mem_filter] at hSx hSy exact hxy (Finset.singleton_injective (hSx.2.symm.trans hSy.2)) have hcsum : 3 * ∑ x, c x ≤ 3 * D.card + 2 * U.card * D.card := by
The sum of criticalities satisfies 3 ∑_{x ∈ V} c(x) ≤ 3 |D| + 2 |U| |D|.
Separate x = v from x ≠ v: trivially c(v) ≤ |D|. For the remaining vertices, summing c(x) ≤ ∑_{w ∈ U} |E(w, x)| and interchanging the order of summation gives ∑_{x ≠ v} c(x) ≤ ∑_{w ∈ U} |{S ∈ D : |S ∩ N[w]| = 1}|. Multiplying by 3 and applying the two-thirds bound to each w ∈ U yields 3 ∑_{x ≠ v} c(x) ≤ 2 |U| |D|. Adding 3 c(v) ≤ 3 |D| gives 3 ∑_{x ∈ V} c(x) ≤ 3 |D| + 2 |U| |D|.
uses
Finset.add_sum_erase,Finset.card_filter_le,Finset.mem_univ,Finset.mul_sum,Finset.ne_of_mem_erase,Finset.sum_comm,Finset.sum_const,Finset.sum_le_sum,smul_eq_mulrw [← Finset.add_sum_erase _ _ (Finset.mem_univ v)] have hcv : c v ≤ D.card := Finset.card_filter_le _ _ have h1 : ∑ x ∈ Finset.univ.erase v, c x ≤ ∑ w ∈ U, (D.filter (fun S => (S ∩ N w).card = 1)).card := by calc ∑ x ∈ Finset.univ.erase v, c x ≤ ∑ x ∈ Finset.univ.erase v, ∑ w ∈ U, (E w x).card := Finset.sum_le_sum fun x hx => hcrit x (Finset.ne_of_mem_erase hx) _ = ∑ w ∈ U, ∑ x ∈ Finset.univ.erase v, (E w x).card := Finset.sum_comm _ ≤ _ := Finset.sum_le_sum fun w _ => hEsum w have h2 : 3 * ∑ w ∈ U, (D.filter (fun S => (S ∩ N w).card = 1)).card ≤ 2 * U.card * D.card := by rw [Finset.mul_sum] calc ∑ w ∈ U, 3 * (D.filter (fun S => (S ∩ N w).card = 1)).card ≤ ∑ w ∈ U, 2 * D.card := Finset.sum_le_sum fun w _ => hthird w _ = 2 * U.card * D.card := by rw [Finset.sum_const, smul_eq_mul]; ring omega
The sum of counts satisfies 2 ∑_{x ∈ V} a(x) = n |D| + ∑_{x ∈ V} c(x).
Summing a(x) + b(x) = |D| over all n vertices gives ∑ a(x) + ∑ b(x) = n |D|. Summing a(x) = b(x) + c(x) over all vertices gives ∑ a(x) = ∑ b(x) + ∑ c(x). Adding these two equations cancels ∑ b(x) and yields 2 ∑ a(x) = n |D| + ∑ c(x).
uses
Finset.card_univ,Finset.sum_add_distrib,Finset.sum_congr,Finset.sum_const,smul_eq_mulhave h2a : 2 * ∑ x, a x = n * D.card + ∑ x, c x := by have e1 : ∑ x, (a x + b x) = n * D.card := by rw [Finset.sum_congr rfl fun x _ => hab x, Finset.sum_const, smul_eq_mul, Finset.card_univ] have e2 : ∑ x, a x = ∑ x, b x + ∑ x, c x := by rw [← Finset.sum_add_distrib]; exact Finset.sum_congr rfl fun x _ => habc x rw [← e1, Finset.sum_add_distrib]; omega
The average size of dominating sets containing v is at most (5n - 2 deg(v) + 1)/6. automation
Since |U| = n - 1 - deg(v), we have |U| + deg(v) + 1 = n. Multiplying the double counting identity by 3 gives 6 ∑_{S ∈ D} |S| = 3 n |D| + 3 ∑ c(x) ≤ 3 n |D| + 3 |D| + 2 |U| |D| = (5n - 2 deg(v) + 1) |D|. Dividing both sides by 6 |D| (which is strictly positive) yields the bound on the local average dominating order. Linear arithmetic closes the goal.
uses
Nat.cast_sum,div_le_div_iff₀-- conclude have hm : U.card + G.degree v + 1 = n := by rw [hUcard]; omega have hDpos : (0 : ℚ) < D.card := by exact_mod_cast hDne.card_pos have qa : (2 : ℚ) * ((∑ x, a x : ℕ) : ℚ) = n * D.card + ((∑ x, c x : ℕ) : ℚ) := by exact_mod_cast h2a have qc : (3 : ℚ) * ((∑ x, c x : ℕ) : ℚ) ≤ 3 * D.card + 2 * U.card * D.card := by exact_mod_cast hcsum have qm : (U.card : ℚ) + G.degree v + 1 = n := by exact_mod_cast hm have qs : ∑ S ∈ D, (S.card : ℚ) = ((∑ x, a x : ℕ) : ℚ) := by rw [← hsum, Nat.cast_sum] have qnD : (n : ℚ) * D.card = U.card * D.card + G.degree v * D.card + D.card := by rw [← qm]; ring unfold simple_graph_local_avg_dominating_order rw [← hD, div_le_div_iff₀ hDpos (by norm_num : (0 : ℚ) < 6), qs] linarith
G.card_neighborFinset_eq_degree- in a simple graph, the number of vertices in the neighbor finset of v equals deg(v)
G.mem_neighborFinset- membership in the neighbor finset of v is equivalent to adjacency to v
G.ne_of_adj- adjacent vertices in a simple graph are not equal
Fintype.card_pos_iff- the cardinality of a finite type is strictly positive if and only if the type is nonempty
Finset.add_sum_erase- separating an element from a sum over a finset: f(a) + ∑_{x ∈ s \ {a}} f(x) = ∑_{x ∈ s} f(x)
Finset.card_biUnion- for disjoint finsets in a family, the cardinality of their union is the sum of their cardinalities
Finset.card_biUnion_le- the cardinality of a union of finsets is at most the sum of their cardinalities
Finset.card_eq_one- a finset has cardinality 1 if and only if it is a singleton {x}
Finset.card_erase_of_mem- erasing an element from a finset decreases its cardinality by 1
Finset.card_filter_add_card_filter_not- the number of elements satisfying a predicate plus the number not satisfying it equals the total cardinality
Finset.card_filter_le- the cardinality of a filtered subset is at most the cardinality of the original finset
Finset.card_filter- the cardinality of a filtered finset equals the sum over the finset of the indicator function
Finset.card_image_of_injOn- an injective map on a finset preserves its cardinality
Finset.card_le_card- a subset has cardinality at most the cardinality of the superset
Finset.card_le_mul_card_image_of_maps_to- if a map from s to t has fibers of size at most n, then |s| ≤ n|t|
Finset.card_le_one- in a finset of cardinality at most 1, any two elements are equal
Finset.card_le_two- a finset with at most two elements has cardinality at most 2
Finset.card_pos- a finset is nonempty if and only if its cardinality is strictly positive
Finset.card_sdiff_of_subset- the cardinality of a finset difference t \ s with s ⊆ t is |t| - |s|
Finset.card_singleton- a singleton finset {a} has cardinality 1
Finset.card_univ- the cardinality of the universal finset Finset.univ equals Fintype.card V
Finset.disjoint_left- two finsets are disjoint if and only if no element of the first belongs to the second
Finset.erase_insert- erasing an element not in a finset after inserting it recovers the original finset
Finset.filter_filter- filtering by p and then by q is equivalent to filtering by p ∧ q
Finset.filter_mem_eq_inter- filtering by membership in another finset is equivalent to set intersection
Finset.insert_erase- inserting an element into a finset from which it was erased recovers the finset
Finset.mem_biUnion- membership in a union of finsets is equivalent to membership in some member finset
Finset.mem_erase- membership in s.erase a is equivalent to being in s and distinct from a
Finset.mem_filter- membership in a filtered finset is equivalent to membership in the finset and satisfying the predicate
Finset.mem_insert_self- an element belongs to the finset obtained by inserting it
Finset.mem_sdiff- membership in a set difference s \ t is membership in s and not in t
Finset.mem_singleton_self- every element belongs to its own singleton finset
Finset.mem_univ- every element of a finite type belongs to the universal finset Finset.univ
Finset.mul_sum- multiplication by a scalar distributes over a finite sum
Finset.ne_of_mem_erase- an element in s.erase a cannot equal a
Finset.singleton_injective- the map sending an element to its singleton finset is injective
Finset.subset_insert- a finset is contained in the finset obtained by inserting any element
Finset.sum_add_distrib- the sum of termwise sums over a finset is the sum of the two sums
Finset.sum_congr- two sums over finsets are equal if the index sets and the terms are equal
Finset.sum_comm- double sums over two finsets can be interchanged
Finset.sum_const- the sum of a constant over a finset equals the cardinality times that constant
Finset.sum_le_sum- termwise inequality implies inequality of sums over a finset
Finset.univ- Finset.univ is the finset of all elements of a finite type
Finset.univ_inter- the intersection of Finset.univ with any finset is the finset itself
Function.onFun- Function.onFun applies a binary operation after applying a unary function to both arguments
Nat.cast_sum- casting a sum of natural numbers to ℚ is the sum of the cast terms
Or.inl- introduction rule for the left disjunct of a disjunction
Or.inr- introduction rule for the right disjunct of a disjunction
congrArg- equality of inputs implies equality of outputs under any function f
div_le_div_iff₀- for positive denominators, a / b ≤ c / d is equivalent to a * d ≤ c * b
if_neg- an if-then-else evaluates to the then-branch when the condition is false
if_pos- an if-then-else evaluates to the then-branch when the condition is true
le_antisymm- antisymmetry of partial orders: a ≤ b and b ≤ a imply a = b
le_trans- transitivity of order: a ≤ b and b ≤ c imply a ≤ c
smul_eq_mul- scalar multiplication of a natural number by a scalar is standard multiplication
- Lean uses dot notation on the graph variable G for G.degree, G.card_neighborFinset_eq_degree, G.ne_of_adj, and G.mem_neighborFinset.
- The term c(x) measures the number of dominating sets in D in which x is critical, meaning S \ {x} is no longer dominating.
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_le_of_no_isolated {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hiso : ∀ w, 0 < G.degree w) (v : V) : simple_graph_local_avg_dominating_order G v ≤ (5 * (Fintype.card V : ℚ) - 2 * G.degree v + 1) / 6 := by classical set D := simple_graph_dominating_sets_containing G v with hD set n := Fintype.card V with hn 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 -- `D` is closed under supersets have hup : ∀ S ∈ D, ∀ T, S ⊆ T → T ∈ D := by intro S hS T hST rw [memD] at hS ⊢ refine ⟨hST hS.1, fun w => ?_⟩ rcases hS.2 w with h | ⟨u, hu, h⟩ · exact Or.inl (hST h) · exact Or.inr ⟨u, hST hu, h⟩ have hDne : D.Nonempty := ⟨Finset.univ, (memD _).2 ⟨Finset.mem_univ v, fun w => Or.inl (Finset.mem_univ w)⟩⟩ -- closed neighbourhoods and the vertices outside `N[v]` set N : V → Finset V := fun w => insert w (G.neighborFinset w) with hN set U : Finset V := (Finset.univ.erase v) \ G.neighborFinset v with hU have hUcard : U.card = n - 1 - G.degree v := by rw [hU, Finset.card_sdiff_of_subset, Finset.card_erase_of_mem (Finset.mem_univ v), G.card_neighborFinset_eq_degree] · rfl · intro w hw rw [Finset.mem_erase] exact ⟨(G.ne_of_adj ((G.mem_neighborFinset v w).1 hw)).symm, Finset.mem_univ w⟩ have hdegle : G.degree v ≤ n - 1 := by rw [← G.card_neighborFinset_eq_degree] have : G.neighborFinset v ⊆ Finset.univ.erase v := by intro w hw rw [Finset.mem_erase] exact ⟨(G.ne_of_adj ((G.mem_neighborFinset v w).1 hw)).symm, Finset.mem_univ w⟩ calc (G.neighborFinset v).card ≤ (Finset.univ.erase v).card := Finset.card_le_card this _ = n - 1 := by rw [Finset.card_erase_of_mem (Finset.mem_univ v)]; rfl have hn1 : 1 ≤ n := Fintype.card_pos_iff.2 ⟨v⟩ -- counts: `a x` sets containing `x`, `b x` avoiding `x`, `c x` sets in which `x` is critical set a : V → ℕ := fun x => (D.filter (fun S => x ∈ S)).card with ha set b : V → ℕ := fun x => (D.filter (fun S => x ∉ S)).card with hb set c : V → ℕ := fun x => (D.filter (fun S => x ∈ S ∧ S.erase x ∉ D)).card with hc have hab : ∀ x, a x + b x = D.card := fun x => Finset.card_filter_add_card_filter_not _ have habc : ∀ x, a x = b x + c x := by intro x simp only [ha, hb, hc] have hsplit : (D.filter (fun S => x ∈ S)).card = ((D.filter (fun S => x ∈ S)).filter (fun S => S.erase x ∈ D)).card + ((D.filter (fun S => x ∈ S)).filter (fun S => ¬ S.erase x ∈ D)).card := (Finset.card_filter_add_card_filter_not _).symm rw [Finset.filter_filter, Finset.filter_filter] at hsplit rw [hsplit] congr 1 -- erasing `x` matches the sets with `x` removable with the sets avoiding `x` apply le_antisymm · have inj : Set.InjOn (fun S : Finset V => S.erase x) ↑(D.filter (fun S => x ∈ S ∧ S.erase x ∈ D)) := by intro S hS T hT h simp only [Finset.mem_coe, Finset.mem_filter] at hS hT rw [← Finset.insert_erase hS.2.1, ← Finset.insert_erase hT.2.1] exact congrArg (insert x) h rw [← Finset.card_image_of_injOn inj] apply Finset.card_le_card intro T hT obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT simp only [Finset.mem_filter] at hS ⊢ exact ⟨hS.2.2, by simp⟩ · have inj : Set.InjOn (fun S : Finset V => insert x S) ↑(D.filter (fun S => x ∉ S)) := by intro S hS T hT h simp only [Finset.mem_coe, Finset.mem_filter] at hS hT rw [← Finset.erase_insert hS.2, ← Finset.erase_insert hT.2] exact congrArg (fun W => Finset.erase W x) h rw [← Finset.card_image_of_injOn inj] apply Finset.card_le_card intro T hT obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT simp only [Finset.mem_filter] at hS ⊢ refine ⟨hup S hS.1 _ (Finset.subset_insert x S), Finset.mem_insert_self x S, ?_⟩ rw [Finset.erase_insert hS.2]; exact hS.1 have hsum : ∑ S ∈ D, S.card = ∑ x, a x := by have h : ∀ S ∈ D, S.card = ∑ x, if x ∈ S then 1 else 0 := by intro S _ rw [← Finset.card_filter, Finset.filter_mem_eq_inter, Finset.univ_inter] rw [Finset.sum_congr rfl h, Finset.sum_comm] refine Finset.sum_congr rfl fun x _ => ?_ simp only [ha]; rw [Finset.card_filter] -- `x ≠ v` critical in `S`: `S` meets some `N[w]`, `w ∉ N[v]`, exactly in `x` set E : V → V → Finset (Finset V) := fun w x => D.filter (fun S => S ∩ N w = {x}) with hE have hcrit : ∀ x, x ≠ v → c x ≤ ∑ w ∈ U, (E w x).card := by intro x hxv simp only [hc] refine le_trans (Finset.card_le_card ?_) Finset.card_biUnion_le intro S hS rw [Finset.mem_filter] at hS obtain ⟨hSD, hxS, hSx⟩ := hS have hvS : v ∈ S.erase x := Finset.mem_erase.2 ⟨hxv.symm, ((memD S).1 hSD).1⟩ rw [memD] at hSx push_neg at hSx obtain ⟨w, hwS, hwadj⟩ := hSx hvS have hNw : S ∩ N w = {x} := by ext y simp only [Finset.mem_inter, hN, Finset.mem_insert, G.mem_neighborFinset, Finset.mem_singleton] constructor · rintro ⟨hyS, hy⟩ by_contra hyx have hy' : y ∈ S.erase x := Finset.mem_erase.2 ⟨hyx, hyS⟩ rcases hy with rfl | hy · exact hwS hy' · exact hwadj y hy' hy.symm · intro hyx rw [hyx] refine ⟨hxS, ?_⟩ rcases ((memD S).1 hSD).2 w with h | ⟨u, hu, h⟩ · left by_contra hne exact hwS (Finset.mem_erase.2 ⟨fun h' => hne h'.symm, h⟩) · right by_cases hux : u = x · rw [← hux]; exact h.symm · exact absurd h (hwadj u (Finset.mem_erase.2 ⟨hux, hu⟩)) have hwU : w ∈ U := by rw [hU, Finset.mem_sdiff, Finset.mem_erase, G.mem_neighborFinset] refine ⟨⟨fun h => hwS (h ▸ hvS), Finset.mem_univ w⟩, fun h => hwadj v hvS h⟩ exact Finset.mem_biUnion.2 ⟨w, hwU, Finset.mem_filter.2 ⟨hSD, hNw⟩⟩ -- at most two thirds of the sets meet `N[w]` in a single vertex have hthird : ∀ w, 3 * (D.filter (fun S => (S ∩ N w).card = 1)).card ≤ 2 * D.card := by intro w obtain ⟨w', hw'⟩ : ∃ w', G.Adj w w' := by have := hiso w rw [← G.card_neighborFinset_eq_degree, Finset.card_pos] at this obtain ⟨w', hw'⟩ := this exact ⟨w', (G.mem_neighborFinset w w').1 hw'⟩ have hww' : w ≠ w' := G.ne_of_adj hw' have hwN : w ∈ N w := by simp [hN] have hw'N : w' ∈ N w := by simp [hN, G.mem_neighborFinset, hw'] set single := D.filter (fun S => (S ∩ N w).card = 1) with hsingle set multi := D.filter (fun S => ¬ (S ∩ N w).card = 1) with hmulti have hsm : single.card + multi.card = D.card := Finset.card_filter_add_card_filter_not _ let φ : Finset V → Finset V := fun S => if w ∈ S then insert w' S else insert w S have hmaps : ∀ S ∈ single, φ S ∈ multi := by intro S hS rw [hsingle, Finset.mem_filter, Finset.card_eq_one] at hS obtain ⟨hSD, z, hz⟩ := hS rw [hmulti, Finset.mem_filter] by_cases hwS : w ∈ S · simp only [φ, if_pos hwS] refine ⟨hup S hSD _ (Finset.subset_insert _ _), fun h1 => ?_⟩ have hw_in : w ∈ insert w' S ∩ N w := Finset.mem_inter.2 ⟨Finset.mem_insert_of_mem hwS, hwN⟩ have hw'_in : w' ∈ insert w' S ∩ N w := Finset.mem_inter.2 ⟨Finset.mem_insert_self _ _, hw'N⟩ exact hww' (Finset.card_le_one.1 h1.le w hw_in w' hw'_in) · simp only [φ, if_neg hwS] refine ⟨hup S hSD _ (Finset.subset_insert _ _), fun h1 => ?_⟩ have hz_in : z ∈ S ∩ N w := by rw [hz]; exact Finset.mem_singleton_self z have hzw : z ≠ w := fun h => hwS (h ▸ (Finset.mem_inter.1 hz_in).1) have hw_in : w ∈ insert w S ∩ N w := Finset.mem_inter.2 ⟨Finset.mem_insert_self _ _, hwN⟩ have hz_in' : z ∈ insert w S ∩ N w := Finset.mem_inter.2 ⟨Finset.mem_insert_of_mem (Finset.mem_inter.1 hz_in).1, (Finset.mem_inter.1 hz_in).2⟩ exact hzw (Finset.card_le_one.1 h1.le z hz_in' w hw_in) have hfib : ∀ M, (single.filter (fun S => φ S = M)).card ≤ 2 := by intro M refine le_trans (Finset.card_le_card (t := {M.erase w', M.erase w}) ?_) Finset.card_le_two intro S hS rw [Finset.mem_filter, hsingle, Finset.mem_filter, Finset.card_eq_one] at hS obtain ⟨⟨_, z, hz⟩, hφ⟩ := hS rw [Finset.mem_insert, Finset.mem_singleton] by_cases hwS : w ∈ S · left simp only [φ, if_pos hwS] at hφ have hw'S : w' ∉ S := by intro h have h1 : w ∈ S ∩ N w := Finset.mem_inter.2 ⟨hwS, hwN⟩ have h2 : w' ∈ S ∩ N w := Finset.mem_inter.2 ⟨h, hw'N⟩ rw [hz, Finset.mem_singleton] at h1 h2 exact hww' (h1.trans h2.symm) rw [← hφ, Finset.erase_insert hw'S] · right simp only [φ, if_neg hwS] at hφ rw [← hφ, Finset.erase_insert hwS] have hle2 : single.card ≤ 2 * multi.card := Finset.card_le_mul_card_image_of_maps_to hmaps 2 (fun M _ => hfib M) omega have hEsum : ∀ w, ∑ x ∈ Finset.univ.erase v, (E w x).card ≤ (D.filter (fun S => (S ∩ N w).card = 1)).card := by intro w rw [← Finset.card_biUnion] · apply Finset.card_le_card intro S hS obtain ⟨x, -, hx⟩ := Finset.mem_biUnion.1 hS rw [hE, Finset.mem_filter] at hx rw [Finset.mem_filter, hx.2, Finset.card_singleton] exact ⟨hx.1, rfl⟩ · intro x _ y _ hxy rw [Function.onFun, Finset.disjoint_left] intro S hSx hSy rw [hE, Finset.mem_filter] at hSx hSy exact hxy (Finset.singleton_injective (hSx.2.symm.trans hSy.2)) have hcsum : 3 * ∑ x, c x ≤ 3 * D.card + 2 * U.card * D.card := by rw [← Finset.add_sum_erase _ _ (Finset.mem_univ v)] have hcv : c v ≤ D.card := Finset.card_filter_le _ _ have h1 : ∑ x ∈ Finset.univ.erase v, c x ≤ ∑ w ∈ U, (D.filter (fun S => (S ∩ N w).card = 1)).card := by calc ∑ x ∈ Finset.univ.erase v, c x ≤ ∑ x ∈ Finset.univ.erase v, ∑ w ∈ U, (E w x).card := Finset.sum_le_sum fun x hx => hcrit x (Finset.ne_of_mem_erase hx) _ = ∑ w ∈ U, ∑ x ∈ Finset.univ.erase v, (E w x).card := Finset.sum_comm _ ≤ _ := Finset.sum_le_sum fun w _ => hEsum w have h2 : 3 * ∑ w ∈ U, (D.filter (fun S => (S ∩ N w).card = 1)).card ≤ 2 * U.card * D.card := by rw [Finset.mul_sum] calc ∑ w ∈ U, 3 * (D.filter (fun S => (S ∩ N w).card = 1)).card ≤ ∑ w ∈ U, 2 * D.card := Finset.sum_le_sum fun w _ => hthird w _ = 2 * U.card * D.card := by rw [Finset.sum_const, smul_eq_mul]; ring omega have h2a : 2 * ∑ x, a x = n * D.card + ∑ x, c x := by have e1 : ∑ x, (a x + b x) = n * D.card := by rw [Finset.sum_congr rfl fun x _ => hab x, Finset.sum_const, smul_eq_mul, Finset.card_univ] have e2 : ∑ x, a x = ∑ x, b x + ∑ x, c x := by rw [← Finset.sum_add_distrib]; exact Finset.sum_congr rfl fun x _ => habc x rw [← e1, Finset.sum_add_distrib]; omega -- conclude have hm : U.card + G.degree v + 1 = n := by rw [hUcard]; omega have hDpos : (0 : ℚ) < D.card := by exact_mod_cast hDne.card_pos have qa : (2 : ℚ) * ((∑ x, a x : ℕ) : ℚ) = n * D.card + ((∑ x, c x : ℕ) : ℚ) := by exact_mod_cast h2a have qc : (3 : ℚ) * ((∑ x, c x : ℕ) : ℚ) ≤ 3 * D.card + 2 * U.card * D.card := by exact_mod_cast hcsum have qm : (U.card : ℚ) + G.degree v + 1 = n := by exact_mod_cast hm have qs : ∑ S ∈ D, (S.card : ℚ) = ((∑ x, a x : ℕ) : ℚ) := by rw [← hsum, Nat.cast_sum] have qnD : (n : ℚ) * D.card = U.card * D.card + G.degree v * D.card + D.card := by rw [← qm]; ring unfold simple_graph_local_avg_dominating_order rw [← hD, div_le_div_iff₀ hDpos (by norm_num : (0 : ℚ) < 6), qs] linarith