AFTD Auto-Formalizing Theoretical Domains

simple_graph_local_avg_dominating_order_lt_of_four_le

theoremverifiedoriginal

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

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.

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

    lines 5–19

    uses Or.inl, Or.inr, Finset.mem_univ

      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)⟩⟩
  2. 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.

    lines 20–38

    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⟩
  3. 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).

    lines 39–86

    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]
  4. 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)|.

    lines 87–143

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

    lines 144–201

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

    lines 202–299

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

    lines 300–336

    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_distrib

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

    lines 337–370

    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_distrib

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

    lines 371–387

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

    lines 388–502

    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

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