simple_graph_local_avg_dominating_order_lt_of_four_le
For n ≥ 4 the upper bound (5n−1)/6 is never attained: if G has order n ≥ 4 and no isolated vertices, then avd_v(G) < (5n−1)/6 for every vertex v.
Statement
theorem simple_graph_local_avg_dominating_order_lt_of_four_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hn : 4 ≤ Fintype.card V) (hiso : ∀ w, 0 < G.degree w) (v : V) : simple_graph_local_avg_dominating_order G v < (5 * (Fintype.card V : ℚ) - 1) / 6
- Related work
- arXiv:2610.11446 (On the local average order of dominating sets), list entry OP-135 (sharpness of the bound (5n−1)/6 of Theorem 3.8 for n ≥ 4); the negation of sharpness. It follows from the bound (2n+1)/3 conjectured here (simple_graph_local_avg_dominating_order_le_two_mul_add_one_div_three), which is below (5n−1)/6 for n ≥ 4.
- Verified
- 27 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.
Read back from the Lean
Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$ with decidable adjacency. Assume that $|V| \ge 4$, that every vertex $w \in V$ has degree strictly positive (i.e., $G$ has no isolated vertices), and let $v \in V$ be a vertex. Then the average cardinality of the dominating sets of $G$ that contain $v$ is strictly less than $(5 |V| - 1) / 6$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that the average size of dominating sets containing v is strictly less than (5n - 1)/6 for any vertex v in a graph without isolated vertices on n ≥ 4 vertices, the proof double-counts dominating sets containing each vertex x. Each such set either remains dominating when x is removed or has x as an indispensable (critical) vertex, establishing that the total size of all dominating sets is (n|D| + ∑_x c(x))/2, where c(x) counts sets in which x is critical. For x ≠ v, critical sets must meet the closed neighborhood of some vertex w outside N[v] in exactly {x}, and an injection argument proves that at most 2/3 of all dominating sets meet N[w] in a single vertex. When deg(v) ≥ 2, this bound directly gives avd_v(G) ≤ (5n + 1 - 2 deg(v))/6 < (5n - 1)/6; when deg(v) = 1, structural analysis of the vertices at distance at least 2 shows that either some vertex has degree at least 2 or two leaves share a critical witness set, strictly sharpening the bound to avd_v(G) < (5n - 1)/6.
The collection D of dominating sets containing v is nonempty and closed under taking supersets.
We define D as the finset of all dominating sets of G containing v, and n as the number of vertices of V. By definition, a set S belongs to D if and only if v ∈ S and every vertex w is in S or has a neighbor in S. Since adding vertices preserves domination and keeps v, any superset of a set in D also belongs to D. Furthermore, the entire vertex set V is dominating and contains v, so D is nonempty.
uses
Or.inl,Or.inr,Finset.mem_univclassical 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 has size n - 1 - deg(v), and deg(v) ≤ n - 1.
We define the closed neighborhood N[w] = {w} ∪ N_G(w) and U = (V \\ {v}) \\ N_G(v), which consists of all vertices outside the closed neighborhood of v. Since the open neighborhood of v is a subset of V \\ {v}, the cardinality of U is |V \\ {v}| - |N_G(v)| = n - 1 - deg(v). Because N_G(v) ⊆ V \\ {v}, its cardinality is at most n - 1, and since V has at least 4 vertices, n ≥ 1.
uses
Finset.card_sdiff_of_subset,Finset.card_erase_of_mem,Finset.mem_univ,G.card_neighborFinset_eq_degree,Finset.mem_erase,G.ne_of_adj,G.mem_neighborFinset,Finset.card_le_card,Fintype.card_pos_iff-- 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, a(x) = b(x) + c(x), and the total size of dominating sets in D is ∑ x, a(x).
Let a(x) count sets in D containing x, b(x) count sets in D avoiding x, and c(x) count sets in D where x is critical (x ∈ S but S \\ {x} ∉ D). Clearly a(x) + b(x) = |D|. A set S ∈ D with x ∈ S either has S \\ {x} ∈ D (removable) or S \\ {x} ∉ D (critical). The operation S ↦ S \\ {x} gives a bijection between the sets in D with x removable and the sets in D avoiding x (the inverse is T ↦ T ∪ {x}, which is in D by superset closure). Hence the number of removable sets is b(x), giving a(x) = b(x) + c(x). Summing the indicator of x ∈ S over S and x swaps sums to show ∑_{S ∈ D} |S| = ∑_x a(x).
uses
Finset.card_filter_add_card_filter_not,Finset.filter_filter,le_antisymm,Finset.insert_erase,congrArg,Finset.card_image_of_injOn,Finset.card_le_card,Finset.mem_image,Finset.erase_insert,Finset.subset_insert,Finset.mem_insert_self,Finset.card_filter,Finset.filter_mem_eq_inter,Finset.univ_inter,Finset.sum_congr,Finset.sum_comm-- 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]
Critical sets for x ≠ v satisfy S ∩ N[w] = {x} for some w ∈ U, and c(x) ≤ ∑_{w ∈ U} |E(w, x)|, with strict inequality if two witnesses share a set.
For any x ≠ v, if S \\ {x} fails to dominate G, there must be some vertex w undominated by S \\ {x}. Since v ∈ S \\ {x}, w cannot be dominated by v, so w ∈ U. Moreover, w is undominated by S \\ {x} precisely when S meets N[w] only in x: S ∩ N[w] = {x}. Defining E(w, x) = {S ∈ D | S ∩ N[w] = {x}}, this gives {S ∈ D | x critical} ⊆ ⋃_{w ∈ U} E(w, x), hence c(x) ≤ ∑_{w ∈ U} |E(w, x)|. If some S belongs to both E(w_1, x) and E(w_2, x) for w_1 ≠ w_2 ∈ U, the intersection of the two sets in the union is nonempty, forcing c(x) + 1 ≤ ∑_{w ∈ U} |E(w, x)|.
uses
Finset.mem_filter,Finset.mem_erase,Finset.mem_inter,Finset.mem_insert,G.mem_neighborFinset,Finset.mem_singleton,Finset.mem_sdiff,Finset.mem_univ,Finset.mem_biUnion,le_trans,Finset.card_le_card,Finset.card_biUnion_le,Finset.insert_erase,Finset.biUnion_insert,Finset.card_union_add_card_inter,Finset.card_pos,Finset.add_sum_erase-- `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 hsubC : ∀ x, x ≠ v → D.filter (fun S => x ∈ S ∧ S.erase x ∉ D) ⊆ U.biUnion (fun w => E w x) := by intro x hxv 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⟩⟩ have hcrit : ∀ x, x ≠ v → c x ≤ ∑ w ∈ U, (E w x).card := fun x hxv => le_trans (Finset.card_le_card (hsubC x hxv)) Finset.card_biUnion_le -- a set with two witnesses for the same critical vertex makes this strict have hcrit_strict : ∀ x, x ≠ v → ∀ w1 ∈ U, ∀ w2 ∈ U, w1 ≠ w2 → ∀ S, S ∈ E w1 x → S ∈ E w2 x → c x + 1 ≤ ∑ w ∈ U, (E w x).card := by intro x hxv w1 hw1 w2 hw2 hne S hS1 hS2 have hU' : U = insert w1 (U.erase w1) := (Finset.insert_erase hw1).symm have hbu : U.biUnion (fun w => E w x) = E w1 x ∪ (U.erase w1).biUnion (fun w => E w x) := by conv_lhs => rw [hU'] rw [Finset.biUnion_insert] have hS' : S ∈ E w1 x ∩ (U.erase w1).biUnion (fun w => E w x) := Finset.mem_inter.2 ⟨hS1, Finset.mem_biUnion.2 ⟨w2, Finset.mem_erase.2 ⟨hne.symm, hw2⟩, hS2⟩⟩ have h1 := Finset.card_union_add_card_inter (E w1 x) ((U.erase w1).biUnion (fun w => E w x)) have h2 : 1 ≤ (E w1 x ∩ (U.erase w1).biUnion (fun w => E w x)).card := Finset.card_pos.2 ⟨S, hS'⟩ have h3 := Finset.card_biUnion_le (s := U.erase w1) (t := fun w => E w x) have h4 := Finset.add_sum_erase U (fun w => (E w x).card) hw1 have h5 : c x ≤ (U.biUnion (fun w => E w x)).card := Finset.card_le_card (hsubC x hxv) rw [hbu] at h5 omega
For any vertex w, at most 2/3 of the dominating sets in D meet N[w] in exactly one vertex.
Since G has no isolated vertices, w has a neighbor w'. Consider the map φ on sets S with |S ∩ N[w]| = 1 defined by adding w' if w ∈ S, and adding w if w ∉ S. In both cases φ(S) meets N[w] in at least two vertices and belongs to D by superset closure. Moreover, any set M can arise from at most two preimages (namely M \\ {w'} or M \\ {w}), so the fibers of φ have size at most 2. Thus the number of singleton-intersection sets is at most twice the number of multiple-intersection sets, which algebraically yields 3 |{S ∈ D | |S ∩ N[w]| = 1}| ≤ 2 |D|.
uses
G.card_neighborFinset_eq_degree,Finset.card_pos,G.mem_neighborFinset,G.ne_of_adj,Finset.card_filter_add_card_filter_not,Finset.mem_filter,Finset.card_eq_one,if_pos,Finset.subset_insert,Finset.mem_inter,Finset.mem_insert_of_mem,Finset.mem_insert_self,Finset.card_le_one,if_neg,Finset.mem_singleton_self,le_trans,Finset.card_le_card,Finset.card_le_two,Finset.mem_insert,Finset.mem_singleton,Finset.erase_insert,Finset.card_le_mul_card_image_of_maps_to-- 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
If deg(w) ≥ 2, the 2/3 neighborhood bound is strictly strengthened: 3 |{S ∈ D | |S ∩ N[w]| = 1}| + 2 ≤ 2 |D|.
When deg(w) ≥ 2, w has at least two neighbors. The full vertex set V has |V ∩ N[w]| ≥ 3, so V is in the target collection of multi-intersection sets. However, V cannot be in the image of φ: if φ(S) = V, then S would miss at most one vertex (w or w'), leaving at least two vertices of N[w] in S, which contradicts |S ∩ N[w]| = 1. Thus φ maps into the multiple-intersection sets excluding V, so the number of singletons is at most 2 (|multi| - 1), which gives the strict bound 3 |single| + 2 ≤ 2 |D|.
uses
G.card_neighborFinset_eq_degree,Finset.card_pos,G.mem_neighborFinset,G.ne_of_adj,Finset.mem_singleton,Finset.card_le_card,Finset.card_singleton,Finset.card_filter_add_card_filter_not,Finset.mem_filter,Finset.mem_univ,Finset.card_le_one,Finset.card_eq_one,Finset.mem_erase,if_pos,Finset.subset_insert,Finset.mem_insert,Finset.mem_inter,Finset.mem_insert_of_mem,Finset.mem_insert_self,if_neg,Finset.mem_singleton_self,le_trans,Finset.card_le_two,Finset.erase_insert,Finset.card_le_mul_card_image_of_maps_to,Finset.card_erase_of_mem-- a neighbourhood with three vertices: the whole vertex set is no image, so it is strict have hthird_strict : ∀ w, 2 ≤ G.degree w → 3 * (D.filter (fun S => (S ∩ N w).card = 1)).card + 2 ≤ 2 * D.card := by intro w hw2 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'] -- two distinct neighbours of `w` have hnb : ∀ z, ∃ y, G.Adj w y ∧ y ≠ z := by intro z by_contra hcon push_neg at hcon have : G.neighborFinset w ⊆ {z} := fun y hy => Finset.mem_singleton.2 (hcon y ((G.mem_neighborFinset w y).1 hy)) have := Finset.card_le_card this rw [G.card_neighborFinset_eq_degree, Finset.card_singleton] at this omega 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 _ have huniv : Finset.univ ∈ multi := by rw [hmulti, Finset.mem_filter] refine ⟨(memD _).2 ⟨Finset.mem_univ v, fun w => Or.inl (Finset.mem_univ w)⟩, fun h1 => ?_⟩ exact hww' (Finset.card_le_one.1 h1.le w (by simp [hwN]) w' (by simp [hw'N])) let φ : Finset V → Finset V := fun S => if w ∈ S then insert w' S else insert w S have hmaps : ∀ S ∈ single, φ S ∈ multi.erase Finset.univ := by intro S hS rw [hsingle, Finset.mem_filter, Finset.card_eq_one] at hS obtain ⟨hSD, z, hz⟩ := hS rw [Finset.mem_erase, hmulti, Finset.mem_filter] by_cases hwS : w ∈ S · simp only [φ, if_pos hwS] refine ⟨fun hU => ?_, hup S hSD _ (Finset.subset_insert _ _), fun h1 => ?_⟩ · obtain ⟨y, hy, hyw'⟩ := hnb w' have hyS : y ∈ S := by have : y ∈ insert w' S := hU ▸ Finset.mem_univ y rcases Finset.mem_insert.1 this with h | h · exact absurd h hyw' · exact h have h1 : w ∈ S ∩ N w := Finset.mem_inter.2 ⟨hwS, hwN⟩ have h2 : y ∈ S ∩ N w := Finset.mem_inter.2 ⟨hyS, by simp [hN, G.mem_neighborFinset, hy]⟩ rw [hz, Finset.mem_singleton] at h1 h2 exact G.ne_of_adj hy (h1.trans h2.symm) · 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] 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) refine ⟨fun hU => ?_, hup S hSD _ (Finset.subset_insert _ _), fun h1 => ?_⟩ · -- two neighbours of `w` other than... at least one differs from `z` obtain ⟨y, hy, hyz⟩ := hnb z have hyS : y ∈ S := by have : y ∈ insert w S := hU ▸ Finset.mem_univ y rcases Finset.mem_insert.1 this with h | h · exact absurd h (G.ne_of_adj hy).symm · exact h have h2 : y ∈ S ∩ N w := Finset.mem_inter.2 ⟨hyS, by simp [hN, G.mem_neighborFinset, hy]⟩ rw [hz, Finset.mem_singleton] at h2 exact hyz h2 · 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.erase Finset.univ).card := Finset.card_le_mul_card_image_of_maps_to hmaps 2 (fun M _ => hfib M) rw [Finset.card_erase_of_mem huniv] at hle2 have : 1 ≤ multi.card := Finset.card_pos.2 ⟨_, huniv⟩ omega
The total criticality sum satisfies 3 ∑_x c(x) ≤ 3 |D| + 2 |U| |D|, and 2 ∑_x a(x) = n |D| + ∑_x c(x).
For each w, the sets E(w, x) across x ≠ v are pairwise disjoint because S ∩ N[w] cannot equal two different singletons {x} and {y}. Thus ∑_{x ≠ v} |E(w, x)| ≤ |{S ∈ D | |S ∩ N[w]| = 1}|. Summing c(x) over x ≠ v and exchanging summation gives ∑_{x ≠ v} c(x) ≤ ∑_{w ∈ U} |{S ∈ D | |S ∩ N[w]| = 1}|. Multiplying by 3 and applying the 2/3 bound yields 3 ∑_{x ≠ v} c(x) ≤ 2 |U| |D|. Adding the trivial bound 3 c(v) ≤ 3 |D| proves 3 ∑_x c(x) ≤ 3 |D| + 2 |U| |D|. Combining a(x) + b(x) = |D| and a(x) - b(x) = c(x) gives 2 ∑_x a(x) = n |D| + ∑_x c(x).
uses
Finset.card_biUnion,Finset.card_le_card,Finset.mem_biUnion,Finset.mem_filter,Finset.card_singleton,Function.onFun,Finset.disjoint_left,Finset.singleton_injective,Finset.add_sum_erase,Finset.mem_univ,Finset.card_filter_le,Finset.sum_le_sum,Finset.ne_of_mem_erase,Finset.sum_comm,Finset.mul_sum,Finset.sum_const,smul_eq_mul,Finset.sum_congr,Finset.card_univ,Finset.sum_add_distribhave 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 -- the strict count, in the two cases
If any vertex in U has degree ≥ 2 or two vertices in U share a critical witness set, then 3 ∑_x c(x) + 1 ≤ 3 |D| + 2 |U| |D|.
If some w_0 ∈ U has degree ≥ 2, the neighborhood bound for w_0 is strictly smaller by 2, which strictly decreases the sum over w ∈ U. Alternatively, if two vertices w_1, w_2 ∈ U share a set S ∈ E(w_1, x) ∩ E(w_2, x) for some x ≠ v, the sum of c(x) over x ≠ v is strictly smaller than the double sum by at least 1. In either case, the total sum inequality is strictly strengthened by at least 1.
uses
Finset.add_sum_erase,Finset.mem_univ,Finset.card_filter_le,Finset.sum_le_sum,Finset.ne_of_mem_erase,Finset.sum_comm,Finset.sum_const,smul_eq_mul,Finset.mul_sum,Finset.sum_lt_sum,Finset.mem_erase,Finset.sum_congr,Finset.card_univ,Finset.sum_add_distribhave hcsum_strict : ((∃ w ∈ U, 2 ≤ G.degree w) ∨ (∃ x, x ≠ v ∧ ∃ w1 ∈ U, ∃ w2 ∈ U, w1 ≠ w2 ∧ ∃ S, S ∈ E w1 x ∧ S ∈ E w2 x)) → 3 * ∑ x, c x + 1 ≤ 3 * D.card + 2 * U.card * D.card := by intro hcase rw [← Finset.add_sum_erase _ _ (Finset.mem_univ v)] have hcv : c v ≤ D.card := Finset.card_filter_le _ _ have hle1 : ∑ 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) have hle2 : ∑ x ∈ Finset.univ.erase v, ∑ w ∈ U, (E w x).card ≤ ∑ w ∈ U, (D.filter (fun S => (S ∩ N w).card = 1)).card := by rw [Finset.sum_comm]; exact Finset.sum_le_sum fun w _ => hEsum w have hle3 : ∑ 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 have hconst : ∑ w ∈ U, 2 * D.card = 2 * U.card * D.card := by rw [Finset.sum_const, smul_eq_mul]; ring rw [← Finset.mul_sum] at hle3 rcases hcase with ⟨w0, hw0U, hw0⟩ | ⟨x0, hx0v, w1, hw1, w2, hw2, hne, S, hS1, hS2⟩ · have hlt : ∑ w ∈ U, 3 * (D.filter (fun S => (S ∩ N w).card = 1)).card < ∑ w ∈ U, 2 * D.card := Finset.sum_lt_sum (fun w _ => hthird w) ⟨w0, hw0U, by have := hthird_strict w0 hw0; omega⟩ rw [← Finset.mul_sum] at hlt omega · have hlt : ∑ x ∈ Finset.univ.erase v, c x < ∑ x ∈ Finset.univ.erase v, ∑ w ∈ U, (E w x).card := Finset.sum_lt_sum (fun x hx => hcrit x (Finset.ne_of_mem_erase hx)) ⟨x0, Finset.mem_erase.2 ⟨hx0v, Finset.mem_univ x0⟩, by have := hcrit_strict x0 hx0v w1 hw1 w2 hw2 hne S hS1 hS2; omega⟩ 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
Case deg(v) ≥ 2: the average order is strictly less than (5n - 1) / 6.
Since |U| = n - 1 - deg(v), we have |U| + deg(v) + 1 = n. The bound 3 ∑_x c(x) ≤ 3 |D| + 2 |U| |D| implies ∑_x c(x) ≤ |D| + (2/3) |U| |D|. Substituting into 2 ∑_x a(x) = n |D| + ∑_x c(x) gives the upper bound avd_v(G) ≤ (5n + 1 - 2 deg(v)) / 6. Since deg(v) ≥ 2, 5n + 1 - 2 deg(v) ≤ 5n - 3 < 5n - 1, which non-linear rational arithmetic confirms.
uses
Nat.cast_sum,div_lt_div_iff₀have hDpos : (0 : ℚ) < D.card := by exact_mod_cast hDne.card_pos have qs : ∑ S ∈ D, (S.card : ℚ) = ((∑ x, a x : ℕ) : ℚ) := by rw [← hsum, Nat.cast_sum] have qa : (2 : ℚ) * ((∑ x, a x : ℕ) : ℚ) = n * D.card + ((∑ x, c x : ℕ) : ℚ) := by exact_mod_cast h2a have hdv : 1 ≤ G.degree v := hiso v have hm : U.card + G.degree v + 1 = n := by rw [hUcard]; omega have qm : (U.card : ℚ) + G.degree v + 1 = n := by exact_mod_cast hm unfold simple_graph_local_avg_dominating_order rw [← hD, div_lt_div_iff₀ hDpos (by norm_num : (0 : ℚ) < 6), qs] by_cases hdeg2 : 2 ≤ G.degree v · -- the bound `(5n - 2 deg v + 1)/6` is already below `(5n - 1)/6` have qc : (3 : ℚ) * ((∑ x, c x : ℕ) : ℚ) ≤ 3 * D.card + 2 * U.card * D.card := by exact_mod_cast hcsum have q2 : (2 : ℚ) ≤ G.degree v := by exact_mod_cast hdeg2 have qnD : (n : ℚ) * D.card = U.card * D.card + G.degree v * D.card + D.card := by rw [← qm]; ring nlinarith
Case deg(v) = 1: the strict criticality bound holds and avd_v(G) < (5n - 1) / 6.
Since G has no isolated vertices, deg(v) = 1, so v has a unique neighbor y. As n ≥ 4, |U| = n - 2 ≥ 2. If some vertex in U has degree ≥ 2, the strict condition holds immediately. Otherwise, every vertex in U has degree 1, meaning every w ∈ U is a leaf with a unique neighbor z ≠ v. If any leaf w ∈ U has its neighbor z in U, then {w, z} is an isolated K_2 component, and the dominating set V \\ {z} witnesses that w is critical for both w and z. If every leaf in U has its neighbor outside U, all leaves in U must have y as their unique neighbor. Picking two distinct leaves w_1, w_2 ∈ U, the set S = V \\ {w_1, w_2} is dominating (since y dominates both leaves) and witnesses that y is critical for both w_1 and w_2. In all subcases, the strict criticality bound 3 ∑_x c(x) + 1 ≤ 3 |D| + 2 |U| |D| holds, which with |U| = n - 2 and deg(v) = 1 implies avd_v(G) ≤ (5n - 1)/6 - 1/(6|D|) < (5n - 1)/6. Non-linear rational arithmetic closes the goal.
uses
Finset.card_eq_one,G.card_neighborFinset_eq_degree,Finset.mem_sdiff,Finset.mem_erase,Finset.mem_singleton,G.mem_neighborFinset,G.ne_of_adj,Finset.mem_univ,Finset.mem_filter,Finset.mem_inter,Finset.mem_insert,Finset.card_pos,Finset.exists_mem_ne· have hdv1 : G.degree v = 1 := by omega -- `v` has a single neighbour `y` obtain ⟨y, hy⟩ : ∃ y, G.neighborFinset v = {y} := by rw [← Finset.card_eq_one, G.card_neighborFinset_eq_degree, hdv1] have hUall : ∀ z, z ∉ U → z = v ∨ z = y := by intro z hz rw [hU, Finset.mem_sdiff, Finset.mem_erase, hy, Finset.mem_singleton] at hz by_cases hzv : z = v · exact Or.inl hzv · right; by_contra hzy; exact hz ⟨⟨hzv, Finset.mem_univ z⟩, hzy⟩ have hvU : v ∉ U := by simp [hU] have hyU : y ∉ U := by rw [hU, Finset.mem_sdiff, hy]; simp have hUcard2 : 2 ≤ U.card := by omega have hcase : (∃ w ∈ U, 2 ≤ G.degree w) ∨ (∃ x, x ≠ v ∧ ∃ w1 ∈ U, ∃ w2 ∈ U, w1 ≠ w2 ∧ ∃ S, S ∈ E w1 x ∧ S ∈ E w2 x) := by by_cases hα : ∃ w ∈ U, 2 ≤ G.degree w · exact Or.inl hα right push_neg at hα -- every vertex of `U` is a leaf have hleaf : ∀ w ∈ U, ∃ z, G.neighborFinset w = {z} := by intro w hw rw [← Finset.card_eq_one, G.card_neighborFinset_eq_degree] have := hiso w; have := hα w hw; omega have hNw : ∀ w z, G.neighborFinset w = {z} → N w = {w, z} := by intro w z h; simp only [hN, h] have hwv : ∀ w ∈ U, ∀ z, G.Adj w z → z ≠ v := by intro w hw z hz hzv rw [hzv] at hz rw [hU, Finset.mem_sdiff, G.mem_neighborFinset] at hw exact hw.2 hz.symm -- a leaf of `U` whose neighbour is in `U`: a `K₂` component have hK2 : ∀ w ∈ U, ∀ z, G.neighborFinset w = {z} → z ∈ U → ∃ x, x ≠ v ∧ ∃ w1 ∈ U, ∃ w2 ∈ U, w1 ≠ w2 ∧ ∃ S, S ∈ E w1 x ∧ S ∈ E w2 x := by intro w hw z hz hzU have hwz : G.Adj w z := (G.mem_neighborFinset w z).1 (by rw [hz]; simp) obtain ⟨z', hz'⟩ := hleaf z hzU have hzw : G.Adj z w := hwz.symm have hz'w : z' = w := by have : w ∈ G.neighborFinset z := (G.mem_neighborFinset z w).2 hzw rw [hz', Finset.mem_singleton] at this; exact this.symm have hne : w ≠ z := G.ne_of_adj hwz have hSD : Finset.univ.erase z ∈ D := by rw [memD] refine ⟨Finset.mem_erase.2 ⟨fun h => hvU (h ▸ hzU), Finset.mem_univ v⟩, fun t => ?_⟩ by_cases htz : t = z · exact Or.inr ⟨w, Finset.mem_erase.2 ⟨hne, Finset.mem_univ w⟩, htz ▸ hwz⟩ · exact Or.inl (Finset.mem_erase.2 ⟨htz, Finset.mem_univ t⟩) refine ⟨w, fun h => hvU (h ▸ hw), w, hw, z, hzU, hne, Finset.univ.erase z, ?_, ?_⟩ · rw [hE, Finset.mem_filter, hNw w z hz] refine ⟨hSD, ?_⟩ ext t; simp only [Finset.mem_inter, Finset.mem_erase, Finset.mem_univ, and_true, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨htz, rfl | rfl⟩ · rfl · exact absurd rfl htz · rintro rfl; exact ⟨hne, Or.inl rfl⟩ · rw [hE, Finset.mem_filter, hNw z w (by rw [hz', hz'w])] refine ⟨hSD, ?_⟩ ext t; simp only [Finset.mem_inter, Finset.mem_erase, Finset.mem_univ, and_true, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨htz, rfl | rfl⟩ · exact absurd rfl htz · rfl · rintro rfl; exact ⟨hne, Or.inr rfl⟩ obtain ⟨w1, hw1⟩ := Finset.card_pos.1 (by omega : 0 < U.card) obtain ⟨z1, hz1⟩ := hleaf w1 hw1 by_cases hz1U : z1 ∈ U · exact hK2 w1 hw1 z1 hz1 hz1U obtain ⟨w2, hw2, hw21⟩ := Finset.exists_mem_ne (by omega : 1 < U.card) w1 obtain ⟨z2, hz2⟩ := hleaf w2 hw2 by_cases hz2U : z2 ∈ U · exact hK2 w2 hw2 z2 hz2 hz2U have hw1z1 : G.Adj w1 z1 := (G.mem_neighborFinset w1 z1).1 (by rw [hz1]; simp) have hw2z2 : G.Adj w2 z2 := (G.mem_neighborFinset w2 z2).1 (by rw [hz2]; simp) have hz1y : z1 = y := (hUall z1 hz1U).resolve_left (hwv w1 hw1 z1 hw1z1) have hz2y : z2 = y := (hUall z2 hz2U).resolve_left (hwv w2 hw2 z2 hw2z2) -- two leaves on `y`: drop both, `y` is critical with both as witnesses set S := (Finset.univ.erase w1).erase w2 with hS have hw1y : w1 ≠ y := fun h => hyU (h ▸ hw1) have hw2y : w2 ≠ y := fun h => hyU (h ▸ hw2) have hSD : S ∈ D := by rw [memD] refine ⟨by simp [hS]; exact ⟨fun h => hvU (h ▸ hw2), fun h => hvU (h ▸ hw1)⟩, fun t => ?_⟩ by_cases ht1 : t = w1 · exact Or.inr ⟨y, by simp [hS]; exact ⟨hw2y.symm, hw1y.symm⟩, ht1 ▸ hz1y ▸ hw1z1.symm⟩ by_cases ht2 : t = w2 · exact Or.inr ⟨y, by simp [hS]; exact ⟨hw2y.symm, hw1y.symm⟩, ht2 ▸ hz2y ▸ hw2z2.symm⟩ exact Or.inl (by simp [hS]; exact ⟨ht2, ht1⟩) have hmem : ∀ w z, w ∈ U → G.neighborFinset w = {z} → z = y → (w = w1 ∨ w = w2) → S ∈ E w y := by intro w z _ hz hzy hw rw [hE, Finset.mem_filter, hNw w z hz, hzy] refine ⟨hSD, ?_⟩ ext t simp only [hS, Finset.mem_inter, Finset.mem_erase, Finset.mem_univ, and_true, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨⟨ht2, ht1⟩, h | h⟩ · rcases hw with rfl | rfl · exact absurd h ht1 · exact absurd h ht2 · exact h · rintro rfl; exact ⟨⟨hw2y.symm, hw1y.symm⟩, Or.inr rfl⟩ exact ⟨y, (G.ne_of_adj ((G.mem_neighborFinset v y).1 (by rw [hy]; simp))).symm, w1, hw1, w2, hw2, hw21.symm, S, hmem w1 z1 hw1 hz1 hz1y (Or.inl rfl), hmem w2 z2 hw2 hz2 hz2y (Or.inr rfl)⟩ have qc : (3 : ℚ) * ((∑ x, c x : ℕ) : ℚ) + 1 ≤ 3 * D.card + 2 * U.card * D.card := by exact_mod_cast hcsum_strict hcase have q1 : (G.degree v : ℚ) = 1 := by exact_mod_cast hdv1 have qnD : (n : ℚ) * D.card = U.card * D.card + G.degree v * D.card + D.card := by rw [← qm]; ring nlinarith
Finset.mem_univ- x is an element of the universal finset univ
Or.inl- constructs a proof of a ∨ b from a proof of a
Or.inr- constructs a proof of a ∨ b from a proof of b
Finset.card_sdiff_of_subset- the cardinality of t \\ s is |t| - |s| when s ⊆ t
Finset.card_erase_of_mem- erasing an element from a finset decreases its cardinality by 1
G.card_neighborFinset_eq_degree- the number of neighbors of v equals the degree of v in G
Finset.mem_erase- a ∈ s.erase b if and only if a ≠ b and a ∈ s
G.ne_of_adj- adjacent vertices in a simple graph are not equal
G.mem_neighborFinset- w is in the neighbor finset of v if and only if G.Adj v w
Finset.card_le_card- if s ⊆ t then |s| ≤ |t|
Fintype.card_pos_iff- the cardinality of a fintype is positive if and only if the type is nonempty
Finset.card_filter_add_card_filter_not- |{x ∈ s | p x}| + |{x ∈ s | ¬ p x}| = |s|
Finset.filter_filter- filtering by p and then by q is equivalent to filtering by p ∧ q
le_antisymm- if a ≤ b and b ≤ a then a = b in a partial order
Finset.insert_erase- inserting an element into s.erase a reconstructs s when a ∈ s
congrArg- equal inputs produce equal outputs under a function f
Finset.card_image_of_injOn- the image of a finset under an injective function on s has the same cardinality as s
Finset.mem_image- y ∈ f '' s if and only if y = f x for some x ∈ s
Finset.erase_insert- erasing a from insert a s gives back s when a ∉ s
Finset.subset_insert- s is a subset of insert a s
Finset.mem_insert_self- a is an element of insert a s
Finset.card_filter- the cardinality of a filtered finset equals the sum of indicator 1s
Finset.filter_mem_eq_inter- filtering s by membership in t gives the intersection s ∩ t
Finset.univ_inter- univ ∩ s = s for any finset s
Finset.sum_congr- sums of equal functions over equal finsets are equal
Finset.sum_comm- interchanging the order of summation in a double sum over finsets
Finset.mem_filter- membership in a filtered finset is conjunction of membership and the predicate
Finset.mem_inter- membership in the intersection s ∩ t is conjunction of memberships
Finset.mem_insert- membership in insert b s is equality to b or membership in s
Finset.mem_singleton- b ∈ {a} if and only if b = a
Finset.mem_sdiff- membership in s \\ t is membership in s and non-membership in t
Finset.mem_biUnion- membership in the union of a family of finsets indexed by s
le_trans- transitivity of ≤ in a preorder
Finset.card_biUnion_le- the cardinality of a bounded union is at most the sum of cardinalities
Finset.biUnion_insert- bounded union over insert a s is t a ∪ bounded union over s
Finset.card_union_add_card_inter- |s ∪ t| + |s ∩ t| = |s| + |t| for finsets
Finset.card_pos- a finset has positive cardinality if and only if it is nonempty
Finset.add_sum_erase- f a + sum over s.erase a equals sum over s when a ∈ s
Finset.card_eq_one- a finset has cardinality 1 if and only if it is a singleton
if_pos- evaluates if c then t else e to t when c holds
Finset.mem_insert_of_mem- if a ∈ s then a ∈ insert b s
Finset.card_le_one- a finset has cardinality at most 1 if all pairs of elements are equal
if_neg- evaluates if c then t else e to e when ¬ c holds
Finset.mem_singleton_self- a is an element of {a}
Finset.card_le_two- any set of at most two elements {a, b} has cardinality ≤ 2
Finset.card_le_mul_card_image_of_maps_to- if fibers of f on s have size at most n then |s| ≤ n * |f '' s|
Finset.card_singleton- a singleton finset has cardinality 1
Finset.card_biUnion- the cardinality of a disjoint bounded union equals the sum of cardinalities
Function.onFun- precomposing a binary relation with a function f
Finset.disjoint_left- disjointness of two finsets means no element of s is in t
Finset.singleton_injective- the singleton set constructor is injective
Finset.card_filter_le- the cardinality of a filtered finset is at most that of the original finset
Finset.sum_le_sum- a sum of pointwise smaller functions is at most the sum of larger functions
Finset.ne_of_mem_erase- if b ∈ s.erase a then b ≠ a
Finset.mul_sum- distributing multiplication over summation
Finset.sum_const- sum of a constant over a finset equals cardinality times the constant
smul_eq_mul- scalar multiplication on ℕ corresponds to ordinary multiplication
Finset.card_univ- the cardinality of univ on V is the fintype cardinality of V
Finset.sum_add_distrib- distributing sum over addition of functions
Finset.sum_lt_sum- sum of strictly smaller function at one element and ≤ elsewhere is strictly smaller
Nat.cast_sum- coercing a sum of natural numbers to an additive monoid with one preserves the sum
div_lt_div_iff₀- a/b < c/d ↔ a*d < c*b for positive denominators in an ordered group with zero
Finset.exists_mem_ne- if a finset has size > 1 then there exists an element distinct from any given element
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.
Lean’s trace was cut to the first 400 of 520 tactics.
theorem simple_graph_local_avg_dominating_order_lt_of_four_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hn : 4 ≤ Fintype.card V) (hiso : ∀ w, 0 < G.degree w) (v : V) : simple_graph_local_avg_dominating_order G v < (5 * (Fintype.card 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 hsubC : ∀ x, x ≠ v → D.filter (fun S => x ∈ S ∧ S.erase x ∉ D) ⊆ U.biUnion (fun w => E w x) := by intro x hxv 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⟩⟩ have hcrit : ∀ x, x ≠ v → c x ≤ ∑ w ∈ U, (E w x).card := fun x hxv => le_trans (Finset.card_le_card (hsubC x hxv)) Finset.card_biUnion_le -- a set with two witnesses for the same critical vertex makes this strict have hcrit_strict : ∀ x, x ≠ v → ∀ w1 ∈ U, ∀ w2 ∈ U, w1 ≠ w2 → ∀ S, S ∈ E w1 x → S ∈ E w2 x → c x + 1 ≤ ∑ w ∈ U, (E w x).card := by intro x hxv w1 hw1 w2 hw2 hne S hS1 hS2 have hU' : U = insert w1 (U.erase w1) := (Finset.insert_erase hw1).symm have hbu : U.biUnion (fun w => E w x) = E w1 x ∪ (U.erase w1).biUnion (fun w => E w x) := by conv_lhs => rw [hU'] rw [Finset.biUnion_insert] have hS' : S ∈ E w1 x ∩ (U.erase w1).biUnion (fun w => E w x) := Finset.mem_inter.2 ⟨hS1, Finset.mem_biUnion.2 ⟨w2, Finset.mem_erase.2 ⟨hne.symm, hw2⟩, hS2⟩⟩ have h1 := Finset.card_union_add_card_inter (E w1 x) ((U.erase w1).biUnion (fun w => E w x)) have h2 : 1 ≤ (E w1 x ∩ (U.erase w1).biUnion (fun w => E w x)).card := Finset.card_pos.2 ⟨S, hS'⟩ have h3 := Finset.card_biUnion_le (s := U.erase w1) (t := fun w => E w x) have h4 := Finset.add_sum_erase U (fun w => (E w x).card) hw1 have h5 : c x ≤ (U.biUnion (fun w => E w x)).card := Finset.card_le_card (hsubC x hxv) rw [hbu] at h5 omega -- 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 -- a neighbourhood with three vertices: the whole vertex set is no image, so it is strict have hthird_strict : ∀ w, 2 ≤ G.degree w → 3 * (D.filter (fun S => (S ∩ N w).card = 1)).card + 2 ≤ 2 * D.card := by intro w hw2 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'] -- two distinct neighbours of `w` have hnb : ∀ z, ∃ y, G.Adj w y ∧ y ≠ z := by intro z by_contra hcon push_neg at hcon have : G.neighborFinset w ⊆ {z} := fun y hy => Finset.mem_singleton.2 (hcon y ((G.mem_neighborFinset w y).1 hy)) have := Finset.card_le_card this rw [G.card_neighborFinset_eq_degree, Finset.card_singleton] at this omega 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 _ have huniv : Finset.univ ∈ multi := by rw [hmulti, Finset.mem_filter] refine ⟨(memD _).2 ⟨Finset.mem_univ v, fun w => Or.inl (Finset.mem_univ w)⟩, fun h1 => ?_⟩ exact hww' (Finset.card_le_one.1 h1.le w (by simp [hwN]) w' (by simp [hw'N])) let φ : Finset V → Finset V := fun S => if w ∈ S then insert w' S else insert w S have hmaps : ∀ S ∈ single, φ S ∈ multi.erase Finset.univ := by intro S hS rw [hsingle, Finset.mem_filter, Finset.card_eq_one] at hS obtain ⟨hSD, z, hz⟩ := hS rw [Finset.mem_erase, hmulti, Finset.mem_filter] by_cases hwS : w ∈ S · simp only [φ, if_pos hwS] refine ⟨fun hU => ?_, hup S hSD _ (Finset.subset_insert _ _), fun h1 => ?_⟩ · obtain ⟨y, hy, hyw'⟩ := hnb w' have hyS : y ∈ S := by have : y ∈ insert w' S := hU ▸ Finset.mem_univ y rcases Finset.mem_insert.1 this with h | h · exact absurd h hyw' · exact h have h1 : w ∈ S ∩ N w := Finset.mem_inter.2 ⟨hwS, hwN⟩ have h2 : y ∈ S ∩ N w := Finset.mem_inter.2 ⟨hyS, by simp [hN, G.mem_neighborFinset, hy]⟩ rw [hz, Finset.mem_singleton] at h1 h2 exact G.ne_of_adj hy (h1.trans h2.symm) · 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] 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) refine ⟨fun hU => ?_, hup S hSD _ (Finset.subset_insert _ _), fun h1 => ?_⟩ · -- two neighbours of `w` other than... at least one differs from `z` obtain ⟨y, hy, hyz⟩ := hnb z have hyS : y ∈ S := by have : y ∈ insert w S := hU ▸ Finset.mem_univ y rcases Finset.mem_insert.1 this with h | h · exact absurd h (G.ne_of_adj hy).symm · exact h have h2 : y ∈ S ∩ N w := Finset.mem_inter.2 ⟨hyS, by simp [hN, G.mem_neighborFinset, hy]⟩ rw [hz, Finset.mem_singleton] at h2 exact hyz h2 · 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.erase Finset.univ).card := Finset.card_le_mul_card_image_of_maps_to hmaps 2 (fun M _ => hfib M) rw [Finset.card_erase_of_mem huniv] at hle2 have : 1 ≤ multi.card := Finset.card_pos.2 ⟨_, huniv⟩ 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 -- the strict count, in the two cases have hcsum_strict : ((∃ w ∈ U, 2 ≤ G.degree w) ∨ (∃ x, x ≠ v ∧ ∃ w1 ∈ U, ∃ w2 ∈ U, w1 ≠ w2 ∧ ∃ S, S ∈ E w1 x ∧ S ∈ E w2 x)) → 3 * ∑ x, c x + 1 ≤ 3 * D.card + 2 * U.card * D.card := by intro hcase rw [← Finset.add_sum_erase _ _ (Finset.mem_univ v)] have hcv : c v ≤ D.card := Finset.card_filter_le _ _ have hle1 : ∑ 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) have hle2 : ∑ x ∈ Finset.univ.erase v, ∑ w ∈ U, (E w x).card ≤ ∑ w ∈ U, (D.filter (fun S => (S ∩ N w).card = 1)).card := by rw [Finset.sum_comm]; exact Finset.sum_le_sum fun w _ => hEsum w have hle3 : ∑ 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 have hconst : ∑ w ∈ U, 2 * D.card = 2 * U.card * D.card := by rw [Finset.sum_const, smul_eq_mul]; ring rw [← Finset.mul_sum] at hle3 rcases hcase with ⟨w0, hw0U, hw0⟩ | ⟨x0, hx0v, w1, hw1, w2, hw2, hne, S, hS1, hS2⟩ · have hlt : ∑ w ∈ U, 3 * (D.filter (fun S => (S ∩ N w).card = 1)).card < ∑ w ∈ U, 2 * D.card := Finset.sum_lt_sum (fun w _ => hthird w) ⟨w0, hw0U, by have := hthird_strict w0 hw0; omega⟩ rw [← Finset.mul_sum] at hlt omega · have hlt : ∑ x ∈ Finset.univ.erase v, c x < ∑ x ∈ Finset.univ.erase v, ∑ w ∈ U, (E w x).card := Finset.sum_lt_sum (fun x hx => hcrit x (Finset.ne_of_mem_erase hx)) ⟨x0, Finset.mem_erase.2 ⟨hx0v, Finset.mem_univ x0⟩, by have := hcrit_strict x0 hx0v w1 hw1 w2 hw2 hne S hS1 hS2; omega⟩ 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 have hDpos : (0 : ℚ) < D.card := by exact_mod_cast hDne.card_pos have qs : ∑ S ∈ D, (S.card : ℚ) = ((∑ x, a x : ℕ) : ℚ) := by rw [← hsum, Nat.cast_sum] have qa : (2 : ℚ) * ((∑ x, a x : ℕ) : ℚ) = n * D.card + ((∑ x, c x : ℕ) : ℚ) := by exact_mod_cast h2a have hdv : 1 ≤ G.degree v := hiso v have hm : U.card + G.degree v + 1 = n := by rw [hUcard]; omega have qm : (U.card : ℚ) + G.degree v + 1 = n := by exact_mod_cast hm unfold simple_graph_local_avg_dominating_order rw [← hD, div_lt_div_iff₀ hDpos (by norm_num : (0 : ℚ) < 6), qs] by_cases hdeg2 : 2 ≤ G.degree v · -- the bound `(5n - 2 deg v + 1)/6` is already below `(5n - 1)/6` have qc : (3 : ℚ) * ((∑ x, c x : ℕ) : ℚ) ≤ 3 * D.card + 2 * U.card * D.card := by exact_mod_cast hcsum have q2 : (2 : ℚ) ≤ G.degree v := by exact_mod_cast hdeg2 have qnD : (n : ℚ) * D.card = U.card * D.card + G.degree v * D.card + D.card := by rw [← qm]; ring nlinarith · have hdv1 : G.degree v = 1 := by omega -- `v` has a single neighbour `y` obtain ⟨y, hy⟩ : ∃ y, G.neighborFinset v = {y} := by rw [← Finset.card_eq_one, G.card_neighborFinset_eq_degree, hdv1] have hUall : ∀ z, z ∉ U → z = v ∨ z = y := by intro z hz rw [hU, Finset.mem_sdiff, Finset.mem_erase, hy, Finset.mem_singleton] at hz by_cases hzv : z = v · exact Or.inl hzv · right; by_contra hzy; exact hz ⟨⟨hzv, Finset.mem_univ z⟩, hzy⟩ have hvU : v ∉ U := by simp [hU] have hyU : y ∉ U := by rw [hU, Finset.mem_sdiff, hy]; simp have hUcard2 : 2 ≤ U.card := by omega have hcase : (∃ w ∈ U, 2 ≤ G.degree w) ∨ (∃ x, x ≠ v ∧ ∃ w1 ∈ U, ∃ w2 ∈ U, w1 ≠ w2 ∧ ∃ S, S ∈ E w1 x ∧ S ∈ E w2 x) := by by_cases hα : ∃ w ∈ U, 2 ≤ G.degree w · exact Or.inl hα right push_neg at hα -- every vertex of `U` is a leaf have hleaf : ∀ w ∈ U, ∃ z, G.neighborFinset w = {z} := by intro w hw rw [← Finset.card_eq_one, G.card_neighborFinset_eq_degree] have := hiso w; have := hα w hw; omega have hNw : ∀ w z, G.neighborFinset w = {z} → N w = {w, z} := by intro w z h; simp only [hN, h] have hwv : ∀ w ∈ U, ∀ z, G.Adj w z → z ≠ v := by intro w hw z hz hzv rw [hzv] at hz rw [hU, Finset.mem_sdiff, G.mem_neighborFinset] at hw exact hw.2 hz.symm -- a leaf of `U` whose neighbour is in `U`: a `K₂` component have hK2 : ∀ w ∈ U, ∀ z, G.neighborFinset w = {z} → z ∈ U → ∃ x, x ≠ v ∧ ∃ w1 ∈ U, ∃ w2 ∈ U, w1 ≠ w2 ∧ ∃ S, S ∈ E w1 x ∧ S ∈ E w2 x := by intro w hw z hz hzU have hwz : G.Adj w z := (G.mem_neighborFinset w z).1 (by rw [hz]; simp) obtain ⟨z', hz'⟩ := hleaf z hzU have hzw : G.Adj z w := hwz.symm have hz'w : z' = w := by have : w ∈ G.neighborFinset z := (G.mem_neighborFinset z w).2 hzw rw [hz', Finset.mem_singleton] at this; exact this.symm have hne : w ≠ z := G.ne_of_adj hwz have hSD : Finset.univ.erase z ∈ D := by rw [memD] refine ⟨Finset.mem_erase.2 ⟨fun h => hvU (h ▸ hzU), Finset.mem_univ v⟩, fun t => ?_⟩ by_cases htz : t = z · exact Or.inr ⟨w, Finset.mem_erase.2 ⟨hne, Finset.mem_univ w⟩, htz ▸ hwz⟩ · exact Or.inl (Finset.mem_erase.2 ⟨htz, Finset.mem_univ t⟩) refine ⟨w, fun h => hvU (h ▸ hw), w, hw, z, hzU, hne, Finset.univ.erase z, ?_, ?_⟩ · rw [hE, Finset.mem_filter, hNw w z hz] refine ⟨hSD, ?_⟩ ext t; simp only [Finset.mem_inter, Finset.mem_erase, Finset.mem_univ, and_true, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨htz, rfl | rfl⟩ · rfl · exact absurd rfl htz · rintro rfl; exact ⟨hne, Or.inl rfl⟩ · rw [hE, Finset.mem_filter, hNw z w (by rw [hz', hz'w])] refine ⟨hSD, ?_⟩ ext t; simp only [Finset.mem_inter, Finset.mem_erase, Finset.mem_univ, and_true, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨htz, rfl | rfl⟩ · exact absurd rfl htz · rfl · rintro rfl; exact ⟨hne, Or.inr rfl⟩ obtain ⟨w1, hw1⟩ := Finset.card_pos.1 (by omega : 0 < U.card) obtain ⟨z1, hz1⟩ := hleaf w1 hw1 by_cases hz1U : z1 ∈ U · exact hK2 w1 hw1 z1 hz1 hz1U obtain ⟨w2, hw2, hw21⟩ := Finset.exists_mem_ne (by omega : 1 < U.card) w1 obtain ⟨z2, hz2⟩ := hleaf w2 hw2 by_cases hz2U : z2 ∈ U · exact hK2 w2 hw2 z2 hz2 hz2U have hw1z1 : G.Adj w1 z1 := (G.mem_neighborFinset w1 z1).1 (by rw [hz1]; simp) have hw2z2 : G.Adj w2 z2 := (G.mem_neighborFinset w2 z2).1 (by rw [hz2]; simp) have hz1y : z1 = y := (hUall z1 hz1U).resolve_left (hwv w1 hw1 z1 hw1z1) have hz2y : z2 = y := (hUall z2 hz2U).resolve_left (hwv w2 hw2 z2 hw2z2) -- two leaves on `y`: drop both, `y` is critical with both as witnesses set S := (Finset.univ.erase w1).erase w2 with hS have hw1y : w1 ≠ y := fun h => hyU (h ▸ hw1) have hw2y : w2 ≠ y := fun h => hyU (h ▸ hw2) have hSD : S ∈ D := by rw [memD] refine ⟨by simp [hS]; exact ⟨fun h => hvU (h ▸ hw2), fun h => hvU (h ▸ hw1)⟩, fun t => ?_⟩ by_cases ht1 : t = w1 · exact Or.inr ⟨y, by simp [hS]; exact ⟨hw2y.symm, hw1y.symm⟩, ht1 ▸ hz1y ▸ hw1z1.symm⟩ by_cases ht2 : t = w2 · exact Or.inr ⟨y, by simp [hS]; exact ⟨hw2y.symm, hw1y.symm⟩, ht2 ▸ hz2y ▸ hw2z2.symm⟩ exact Or.inl (by simp [hS]; exact ⟨ht2, ht1⟩) have hmem : ∀ w z, w ∈ U → G.neighborFinset w = {z} → z = y → (w = w1 ∨ w = w2) → S ∈ E w y := by intro w z _ hz hzy hw rw [hE, Finset.mem_filter, hNw w z hz, hzy] refine ⟨hSD, ?_⟩ ext t simp only [hS, Finset.mem_inter, Finset.mem_erase, Finset.mem_univ, and_true, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨⟨ht2, ht1⟩, h | h⟩ · rcases hw with rfl | rfl · exact absurd h ht1 · exact absurd h ht2 · exact h · rintro rfl; exact ⟨⟨hw2y.symm, hw1y.symm⟩, Or.inr rfl⟩ exact ⟨y, (G.ne_of_adj ((G.mem_neighborFinset v y).1 (by rw [hy]; simp))).symm, w1, hw1, w2, hw2, hw21.symm, S, hmem w1 z1 hw1 hz1 hz1y (Or.inl rfl), hmem w2 z2 hw2 hz2 hz2y (Or.inr rfl)⟩ have qc : (3 : ℚ) * ((∑ x, c x : ℕ) : ℚ) + 1 ≤ 3 * D.card + 2 * U.card * D.card := by exact_mod_cast hcsum_strict hcase have q1 : (G.degree v : ℚ) = 1 := by exact_mod_cast hdv1 have qnD : (n : ℚ) * D.card = U.card * D.card + G.degree v * D.card + D.card := by rw [← qm]; ring nlinarith