AFTD Auto-Formalizing Theoretical Domains

simple_graph_local_avg_dominating_order_le_of_no_isolated

theoremverifiedformalization

If the finite graph G of order n has no isolated vertices, then for every vertex v the dominating sets containing v have average size at most (5n − 2 deg(v) + 1)/6 (hence at most (5n − 1)/6).

Statement

theorem simple_graph_local_avg_dominating_order_le_of_no_isolated {V : Type*} [Fintype V]
    [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hiso : ∀ w, 0 < G.degree w)
    (v : V) :
    simple_graph_local_avg_dominating_order G v ≤
      (5 * (Fintype.card V : ℚ) - 2 * G.degree v + 1) / 6
Formalizes
arXiv:2610.11446 (On the local average order of dominating sets), Theorem 3.8, second statement (the first, the sum bound (n+1)/2 + ½ Σ_{u ∉ N[v]} (deg u + 1)/(2^{deg u + 1} − 1), is not stated here).
Verified
09 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

The theorem bounds the average size of dominating sets containing a designated vertex v in a graph without isolated vertices. By decomposing dominating sets containing x into those where x is removable and those where x is critical, we obtain the identity 2 ∑ a(x) = n |D| + ∑ c(x). For x ≠ v, criticality requires the dominating set to meet the closed neighborhood of some vertex w ∉ N[v] in exactly {x}, and a 2-to-1 map shows that at most two-thirds of dominating sets meet N[w] in a single vertex. Combining these bounds yields 3 ∑ c(x) ≤ 3 |D| + 2 (n - 1 - deg(v)) |D|, from which the upper bound (5n - 2 deg(v) + 1)/6 follows immediately.

  1. The family D of dominating sets containing v is nonempty, characterized by domination of every vertex, and closed under taking supersets.

    We define D as the collection of dominating sets containing v and n as |V|. A set S is in D if and only if v ∈ S and every vertex w is in S or has a neighbor in S. If S ∈ D and S ⊆ T, then v ∈ T and every vertex dominated by S is also dominated by T, so T ∈ D. The universal set Finset.univ dominates every vertex and contains v, so D is nonempty.

    lines 6–20

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

      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 alone has cardinality |U| = n - 1 - deg(v), and deg(v) ≤ n - 1.

    For any w, N[w] denotes the closed neighborhood {w} ∪ N(w). The set U = (V \ {v}) \ N(v) consists of all vertices other than v that are not adjacent to v. Since the neighbor set N(v) has size deg(v) and is disjoint from {v}, subtracting its size from |V \ {v}| = n - 1 yields |U| = n - 1 - deg(v). Because N(v) ⊆ V \ {v}, we also have deg(v) ≤ n - 1, and V is nonempty since it contains v.

    lines 21–39

    uses Finset.card_erase_of_mem, Finset.card_le_card, Finset.card_sdiff_of_subset, Finset.mem_erase, Finset.mem_univ, Fintype.card_pos_iff, G.card_neighborFinset_eq_degree, G.mem_neighborFinset, G.ne_of_adj

      -- closed neighbourhoods and the vertices outside `N[v]`
      set N : V → Finset V := fun w => insert w (G.neighborFinset w) with hN
      set U : Finset V := (Finset.univ.erase v) \ G.neighborFinset v with hU
      have hUcard : U.card = n - 1 - G.degree v := by
        rw [hU, Finset.card_sdiff_of_subset, Finset.card_erase_of_mem (Finset.mem_univ v),
          G.card_neighborFinset_eq_degree]
        · rfl
        · intro w hw
          rw [Finset.mem_erase]
          exact ⟨(G.ne_of_adj ((G.mem_neighborFinset v w).1 hw)).symm, Finset.mem_univ w⟩
      have hdegle : G.degree v ≤ n - 1 := by
        rw [← G.card_neighborFinset_eq_degree]
        have : G.neighborFinset v ⊆ Finset.univ.erase v := by
          intro w hw
          rw [Finset.mem_erase]
          exact ⟨(G.ne_of_adj ((G.mem_neighborFinset v w).1 hw)).symm, Finset.mem_univ w⟩
        calc (G.neighborFinset v).card ≤ (Finset.univ.erase v).card := Finset.card_le_card this
          _ = n - 1 := by rw [Finset.card_erase_of_mem (Finset.mem_univ v)]; rfl
      have hn1 : 1 ≤ n := Fintype.card_pos_iff.2 ⟨v⟩
  3. For each vertex x, the number a(x) of dominating sets containing x equals the number b(x) avoiding x plus the number c(x) in which x is critical: a(x) = b(x) + c(x).

    We partition {S ∈ D : x ∈ S} into those where S \ {x} is still in D and those where S \ {x} ∉ D. The latter sets are precisely those where x is critical, of which there are c(x). The former sets are in bijection with dominating sets avoiding x via S ↦ S \ {x}, with inverse T ↦ T ∪ {x} (which remains in D because D is closed under supersets). Hence their size is b(x), giving a(x) = b(x) + c(x). Together with a(x) + b(x) = |D|, this is the key splitting identity.

    lines 40–80

    uses Finset.card_filter_add_card_filter_not, Finset.card_image_of_injOn, Finset.card_le_card, Finset.erase_insert, Finset.filter_filter, Finset.insert_erase, Finset.mem_insert_self, Finset.subset_insert, congrArg, le_antisymm

      -- counts: `a x` sets containing `x`, `b x` avoiding `x`, `c x` sets in which `x` is critical
      set a : V → ℕ := fun x => (D.filter (fun S => x ∈ S)).card with ha
      set b : V → ℕ := fun x => (D.filter (fun S => x ∉ S)).card with hb
      set c : V → ℕ := fun x => (D.filter (fun S => x ∈ S ∧ S.erase x ∉ D)).card with hc
      have hab : ∀ x, a x + b x = D.card := fun x => Finset.card_filter_add_card_filter_not _
      have habc : ∀ x, a x = b x + c x := by
        intro x
        simp only [ha, hb, hc]
        have hsplit : (D.filter (fun S => x ∈ S)).card =
            ((D.filter (fun S => x ∈ S)).filter (fun S => S.erase x ∈ D)).card +
            ((D.filter (fun S => x ∈ S)).filter (fun S => ¬ S.erase x ∈ D)).card :=
          (Finset.card_filter_add_card_filter_not _).symm
        rw [Finset.filter_filter, Finset.filter_filter] at hsplit
        rw [hsplit]
        congr 1
        -- erasing `x` matches the sets with `x` removable with the sets avoiding `x`
        apply le_antisymm
        · have inj : Set.InjOn (fun S : Finset V => S.erase x)
              ↑(D.filter (fun S => x ∈ S ∧ S.erase x ∈ D)) := by
            intro S hS T hT h
            simp only [Finset.mem_coe, Finset.mem_filter] at hS hT
            rw [← Finset.insert_erase hS.2.1, ← Finset.insert_erase hT.2.1]
            exact congrArg (insert x) h
          rw [← Finset.card_image_of_injOn inj]
          apply Finset.card_le_card
          intro T hT
          obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT
          simp only [Finset.mem_filter] at hS ⊢
          exact ⟨hS.2.2, by simp⟩
        · have inj : Set.InjOn (fun S : Finset V => insert x S) ↑(D.filter (fun S => x ∉ S)) := by
            intro S hS T hT h
            simp only [Finset.mem_coe, Finset.mem_filter] at hS hT
            rw [← Finset.erase_insert hS.2, ← Finset.erase_insert hT.2]
            exact congrArg (fun W => Finset.erase W x) h
          rw [← Finset.card_image_of_injOn inj]
          apply Finset.card_le_card
          intro T hT
          obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT
          simp only [Finset.mem_filter] at hS ⊢
          refine ⟨hup S hS.1 _ (Finset.subset_insert x S), Finset.mem_insert_self x S, ?_⟩
          rw [Finset.erase_insert hS.2]; exact hS.1
  4. The sum of the sizes of all dominating sets in D equals ∑_{x ∈ V} a(x).

    Each set cardinality |S| can be expressed as the sum of indicator values ∑_{x ∈ V} [x ∈ S]. Interchanging the summation over S ∈ D and x ∈ V double counts the pairs (x, S) with x ∈ S, yielding ∑_{S ∈ D} |S| = ∑_{x ∈ V} a(x).

    lines 81–87

    uses Finset.card_filter, Finset.filter_mem_eq_inter, Finset.sum_comm, Finset.sum_congr, Finset.univ_inter

      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]
  5. For x ≠ v, every dominating set in which x is critical meets N[w] in exactly {x} for some w ∈ U, so c(x) ≤ ∑_{w ∈ U} |E(w, x)|.

    If x ≠ v and x is critical in S, then S \ {x} contains v but fails to dominate the whole graph. Some vertex w is not dominated by S \ {x}, so S \ {x} is disjoint from N[w]. Since S dominated w, x must dominate w, meaning S ∩ N[w] = {x}. Moreover, w cannot be v (since v ∈ S \ {x}) nor adjacent to v (since v would dominate w), which places w in U. By the union bound, c(x) ≤ ∑_{w ∈ U} |E(w, x)|.

    lines 88–126

    uses Finset.card_biUnion_le, Finset.card_le_card, Finset.mem_biUnion, Finset.mem_erase, Finset.mem_filter, Finset.mem_sdiff, Finset.mem_univ, G.mem_neighborFinset, le_trans

      -- `x ≠ v` critical in `S`: `S` meets some `N[w]`, `w ∉ N[v]`, exactly in `x`
      set E : V → V → Finset (Finset V) := fun w x => D.filter (fun S => S ∩ N w = {x}) with hE
      have hcrit : ∀ x, x ≠ v → c x ≤ ∑ w ∈ U, (E w x).card := by
        intro x hxv
        simp only [hc]
        refine le_trans (Finset.card_le_card ?_) Finset.card_biUnion_le
        intro S hS
        rw [Finset.mem_filter] at hS
        obtain ⟨hSD, hxS, hSx⟩ := hS
        have hvS : v ∈ S.erase x := Finset.mem_erase.2 ⟨hxv.symm, ((memD S).1 hSD).1⟩
        rw [memD] at hSx
        push_neg at hSx
        obtain ⟨w, hwS, hwadj⟩ := hSx hvS
        have hNw : S ∩ N w = {x} := by
          ext y
          simp only [Finset.mem_inter, hN, Finset.mem_insert, G.mem_neighborFinset,
            Finset.mem_singleton]
          constructor
          · rintro ⟨hyS, hy⟩
            by_contra hyx
            have hy' : y ∈ S.erase x := Finset.mem_erase.2 ⟨hyx, hyS⟩
            rcases hy with rfl | hy
            · exact hwS hy'
            · exact hwadj y hy' hy.symm
          · intro hyx
            rw [hyx]
            refine ⟨hxS, ?_⟩
            rcases ((memD S).1 hSD).2 w with h | ⟨u, hu, h⟩
            · left
              by_contra hne
              exact hwS (Finset.mem_erase.2 ⟨fun h' => hne h'.symm, h⟩)
            · right
              by_cases hux : u = x
              · rw [← hux]; exact h.symm
              · exact absurd h (hwadj u (Finset.mem_erase.2 ⟨hux, hu⟩))
        have hwU : w ∈ U := by
          rw [hU, Finset.mem_sdiff, Finset.mem_erase, G.mem_neighborFinset]
          refine ⟨⟨fun h => hwS (h ▸ hvS), Finset.mem_univ w⟩, fun h => hwadj v hvS h⟩
        exact Finset.mem_biUnion.2 ⟨w, hwU, Finset.mem_filter.2 ⟨hSD, hNw⟩⟩
  6. For every vertex w, at most two-thirds of the dominating sets in D meet N[w] in exactly one vertex: 3 |{S ∈ D : |S ∩ N[w]| = 1}| ≤ 2 |D|.

    Since G has no isolated vertices, w has a neighbor w'. We partition D into sets meeting N[w] in 1 vertex ('single') and those meeting N[w] in a different number of vertices ('multi'). Define φ on 'single' by adding w' if w ∈ S, and adding w if w ∉ S. By superset closure, φ(S) ∈ D, and its intersection with N[w] has size at least 2, so φ(S) ∈ 'multi'. Each target set has at most two preimages (erasing w' or erasing w). Thus |single| ≤ 2 |multi|. Combining this with |single| + |multi| = |D| yields 3 |single| ≤ 2 |D|.

    lines 127–184

    uses Finset.card_eq_one, Finset.card_filter_add_card_filter_not, Finset.card_le_mul_card_image_of_maps_to, Finset.card_le_one, Finset.card_le_two, Finset.card_pos, Finset.erase_insert, Finset.mem_singleton_self, Finset.subset_insert, G.card_neighborFinset_eq_degree, G.mem_neighborFinset, G.ne_of_adj, if_neg, if_pos, le_trans

      -- at most two thirds of the sets meet `N[w]` in a single vertex
      have hthird : ∀ w, 3 * (D.filter (fun S => (S ∩ N w).card = 1)).card ≤ 2 * D.card := by
        intro w
        obtain ⟨w', hw'⟩ : ∃ w', G.Adj w w' := by
          have := hiso w
          rw [← G.card_neighborFinset_eq_degree, Finset.card_pos] at this
          obtain ⟨w', hw'⟩ := this
          exact ⟨w', (G.mem_neighborFinset w w').1 hw'⟩
        have hww' : w ≠ w' := G.ne_of_adj hw'
        have hwN : w ∈ N w := by simp [hN]
        have hw'N : w' ∈ N w := by simp [hN, G.mem_neighborFinset, hw']
        set single := D.filter (fun S => (S ∩ N w).card = 1) with hsingle
        set multi := D.filter (fun S => ¬ (S ∩ N w).card = 1) with hmulti
        have hsm : single.card + multi.card = D.card := Finset.card_filter_add_card_filter_not _
        let φ : Finset V → Finset V := fun S => if w ∈ S then insert w' S else insert w S
        have hmaps : ∀ S ∈ single, φ S ∈ multi := by
          intro S hS
          rw [hsingle, Finset.mem_filter, Finset.card_eq_one] at hS
          obtain ⟨hSD, z, hz⟩ := hS
          rw [hmulti, Finset.mem_filter]
          by_cases hwS : w ∈ S
          · simp only [φ, if_pos hwS]
            refine ⟨hup S hSD _ (Finset.subset_insert _ _), fun h1 => ?_⟩
            have hw_in : w ∈ insert w' S ∩ N w := Finset.mem_inter.2 ⟨Finset.mem_insert_of_mem hwS, hwN⟩
            have hw'_in : w' ∈ insert w' S ∩ N w := Finset.mem_inter.2 ⟨Finset.mem_insert_self _ _, hw'N⟩
            exact hww' (Finset.card_le_one.1 h1.le w hw_in w' hw'_in)
          · simp only [φ, if_neg hwS]
            refine ⟨hup S hSD _ (Finset.subset_insert _ _), fun h1 => ?_⟩
            have hz_in : z ∈ S ∩ N w := by rw [hz]; exact Finset.mem_singleton_self z
            have hzw : z ≠ w := fun h => hwS (h ▸ (Finset.mem_inter.1 hz_in).1)
            have hw_in : w ∈ insert w S ∩ N w := Finset.mem_inter.2 ⟨Finset.mem_insert_self _ _, hwN⟩
            have hz_in' : z ∈ insert w S ∩ N w :=
              Finset.mem_inter.2 ⟨Finset.mem_insert_of_mem (Finset.mem_inter.1 hz_in).1,
                (Finset.mem_inter.1 hz_in).2⟩
            exact hzw (Finset.card_le_one.1 h1.le z hz_in' w hw_in)
        have hfib : ∀ M, (single.filter (fun S => φ S = M)).card ≤ 2 := by
          intro M
          refine le_trans (Finset.card_le_card (t := {M.erase w', M.erase w}) ?_) Finset.card_le_two
          intro S hS
          rw [Finset.mem_filter, hsingle, Finset.mem_filter, Finset.card_eq_one] at hS
          obtain ⟨⟨_, z, hz⟩, hφ⟩ := hS
          rw [Finset.mem_insert, Finset.mem_singleton]
          by_cases hwS : w ∈ S
          · left
            simp only [φ, if_pos hwS] at hφ
            have hw'S : w' ∉ S := by
              intro h
              have h1 : w ∈ S ∩ N w := Finset.mem_inter.2 ⟨hwS, hwN⟩
              have h2 : w' ∈ S ∩ N w := Finset.mem_inter.2 ⟨h, hw'N⟩
              rw [hz, Finset.mem_singleton] at h1 h2
              exact hww' (h1.trans h2.symm)
            rw [← hφ, Finset.erase_insert hw'S]
          · right
            simp only [φ, if_neg hwS] at hφ
            rw [← hφ, Finset.erase_insert hwS]
        have hle2 : single.card ≤ 2 * multi.card :=
          Finset.card_le_mul_card_image_of_maps_to hmaps 2 (fun M _ => hfib M)
        omega
  7. For each vertex w, the sets E(w, x) for x ≠ v are pairwise disjoint, so ∑_{x ≠ v} |E(w, x)| ≤ |{S ∈ D : |S ∩ N[w]| = 1}|.

    If S ∈ E(w, x) ∩ E(w, y), then S ∩ N[w] is both {x} and {y}, so x = y by injectivity of singletons. Thus the sets E(w, x) are pairwise disjoint. Moreover, every S ∈ E(w, x) satisfies |S ∩ N[w]| = 1. The sum of the cardinalities of disjoint subsets is the cardinality of their union, which is bounded by the cardinality of the ambient family.

    lines 185–200

    uses Finset.card_biUnion, Finset.card_le_card, Finset.card_singleton, Finset.disjoint_left, Finset.mem_biUnion, Finset.mem_filter, Finset.singleton_injective, Function.onFun

      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
  8. The sum of criticalities satisfies 3 ∑_{x ∈ V} c(x) ≤ 3 |D| + 2 |U| |D|.

    Separate x = v from x ≠ v: trivially c(v) ≤ |D|. For the remaining vertices, summing c(x) ≤ ∑_{w ∈ U} |E(w, x)| and interchanging the order of summation gives ∑_{x ≠ v} c(x) ≤ ∑_{w ∈ U} |{S ∈ D : |S ∩ N[w]| = 1}|. Multiplying by 3 and applying the two-thirds bound to each w ∈ U yields 3 ∑_{x ≠ v} c(x) ≤ 2 |U| |D|. Adding 3 c(v) ≤ 3 |D| gives 3 ∑_{x ∈ V} c(x) ≤ 3 |D| + 2 |U| |D|.

    lines 201–214

    uses Finset.add_sum_erase, Finset.card_filter_le, Finset.mem_univ, Finset.mul_sum, Finset.ne_of_mem_erase, Finset.sum_comm, Finset.sum_const, Finset.sum_le_sum, smul_eq_mul

        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
  9. The sum of counts satisfies 2 ∑_{x ∈ V} a(x) = n |D| + ∑_{x ∈ V} c(x).

    Summing a(x) + b(x) = |D| over all n vertices gives ∑ a(x) + ∑ b(x) = n |D|. Summing a(x) = b(x) + c(x) over all vertices gives ∑ a(x) = ∑ b(x) + ∑ c(x). Adding these two equations cancels ∑ b(x) and yields 2 ∑ a(x) = n |D| + ∑ c(x).

    lines 215–220

    uses Finset.card_univ, Finset.sum_add_distrib, Finset.sum_congr, Finset.sum_const, smul_eq_mul

      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
  10. The average size of dominating sets containing v is at most (5n - 2 deg(v) + 1)/6. automation

    Since |U| = n - 1 - deg(v), we have |U| + deg(v) + 1 = n. Multiplying the double counting identity by 3 gives 6 ∑_{S ∈ D} |S| = 3 n |D| + 3 ∑ c(x) ≤ 3 n |D| + 3 |D| + 2 |U| |D| = (5n - 2 deg(v) + 1) |D|. Dividing both sides by 6 |D| (which is strictly positive) yields the bound on the local average dominating order. Linear arithmetic closes the goal.

    lines 221–234

    uses Nat.cast_sum, div_le_div_iff₀

      -- conclude
      have hm : U.card + G.degree v + 1 = n := by rw [hUcard]; omega
      have hDpos : (0 : ℚ) < D.card := by exact_mod_cast hDne.card_pos
      have qa : (2 : ℚ) * ((∑ x, a x : ℕ) : ℚ) = n * D.card + ((∑ x, c x : ℕ) : ℚ) := by
        exact_mod_cast h2a
      have qc : (3 : ℚ) * ((∑ x, c x : ℕ) : ℚ) ≤ 3 * D.card + 2 * U.card * D.card := by
        exact_mod_cast hcsum
      have qm : (U.card : ℚ) + G.degree v + 1 = n := by exact_mod_cast hm
      have qs : ∑ S ∈ D, (S.card : ℚ) = ((∑ x, a x : ℕ) : ℚ) := by rw [← hsum, Nat.cast_sum]
      have qnD : (n : ℚ) * D.card = U.card * D.card + G.degree v * D.card + D.card := by
        rw [← qm]; ring
      unfold simple_graph_local_avg_dominating_order
      rw [← hD, div_le_div_iff₀ hDpos (by norm_num : (0 : ℚ) < 6), qs]
      linarith
G.card_neighborFinset_eq_degree
in a simple graph, the number of vertices in the neighbor finset of v equals deg(v)
G.mem_neighborFinset
membership in the neighbor finset of v is equivalent to adjacency to v
G.ne_of_adj
adjacent vertices in a simple graph are not equal
Fintype.card_pos_iff
the cardinality of a finite type is strictly positive if and only if the type is nonempty
Finset.add_sum_erase
separating an element from a sum over a finset: f(a) + ∑_{x ∈ s \ {a}} f(x) = ∑_{x ∈ s} f(x)
Finset.card_biUnion
for disjoint finsets in a family, the cardinality of their union is the sum of their cardinalities
Finset.card_biUnion_le
the cardinality of a union of finsets is at most the sum of their cardinalities
Finset.card_eq_one
a finset has cardinality 1 if and only if it is a singleton {x}
Finset.card_erase_of_mem
erasing an element from a finset decreases its cardinality by 1
Finset.card_filter_add_card_filter_not
the number of elements satisfying a predicate plus the number not satisfying it equals the total cardinality
Finset.card_filter_le
the cardinality of a filtered subset is at most the cardinality of the original finset
Finset.card_filter
the cardinality of a filtered finset equals the sum over the finset of the indicator function
Finset.card_image_of_injOn
an injective map on a finset preserves its cardinality
Finset.card_le_card
a subset has cardinality at most the cardinality of the superset
Finset.card_le_mul_card_image_of_maps_to
if a map from s to t has fibers of size at most n, then |s| ≤ n|t|
Finset.card_le_one
in a finset of cardinality at most 1, any two elements are equal
Finset.card_le_two
a finset with at most two elements has cardinality at most 2
Finset.card_pos
a finset is nonempty if and only if its cardinality is strictly positive
Finset.card_sdiff_of_subset
the cardinality of a finset difference t \ s with s ⊆ t is |t| - |s|
Finset.card_singleton
a singleton finset {a} has cardinality 1
Finset.card_univ
the cardinality of the universal finset Finset.univ equals Fintype.card V
Finset.disjoint_left
two finsets are disjoint if and only if no element of the first belongs to the second
Finset.erase_insert
erasing an element not in a finset after inserting it recovers the original finset
Finset.filter_filter
filtering by p and then by q is equivalent to filtering by p ∧ q
Finset.filter_mem_eq_inter
filtering by membership in another finset is equivalent to set intersection
Finset.insert_erase
inserting an element into a finset from which it was erased recovers the finset
Finset.mem_biUnion
membership in a union of finsets is equivalent to membership in some member finset
Finset.mem_erase
membership in s.erase a is equivalent to being in s and distinct from a
Finset.mem_filter
membership in a filtered finset is equivalent to membership in the finset and satisfying the predicate
Finset.mem_insert_self
an element belongs to the finset obtained by inserting it
Finset.mem_sdiff
membership in a set difference s \ t is membership in s and not in t
Finset.mem_singleton_self
every element belongs to its own singleton finset
Finset.mem_univ
every element of a finite type belongs to the universal finset Finset.univ
Finset.mul_sum
multiplication by a scalar distributes over a finite sum
Finset.ne_of_mem_erase
an element in s.erase a cannot equal a
Finset.singleton_injective
the map sending an element to its singleton finset is injective
Finset.subset_insert
a finset is contained in the finset obtained by inserting any element
Finset.sum_add_distrib
the sum of termwise sums over a finset is the sum of the two sums
Finset.sum_congr
two sums over finsets are equal if the index sets and the terms are equal
Finset.sum_comm
double sums over two finsets can be interchanged
Finset.sum_const
the sum of a constant over a finset equals the cardinality times that constant
Finset.sum_le_sum
termwise inequality implies inequality of sums over a finset
Finset.univ
Finset.univ is the finset of all elements of a finite type
Finset.univ_inter
the intersection of Finset.univ with any finset is the finset itself
Function.onFun
Function.onFun applies a binary operation after applying a unary function to both arguments
Nat.cast_sum
casting a sum of natural numbers to ℚ is the sum of the cast terms
Or.inl
introduction rule for the left disjunct of a disjunction
Or.inr
introduction rule for the right disjunct of a disjunction
congrArg
equality of inputs implies equality of outputs under any function f
div_le_div_iff₀
for positive denominators, a / b ≤ c / d is equivalent to a * d ≤ c * b
if_neg
an if-then-else evaluates to the then-branch when the condition is false
if_pos
an if-then-else evaluates to the then-branch when the condition is true
le_antisymm
antisymmetry of partial orders: a ≤ b and b ≤ a imply a = b
le_trans
transitivity of order: a ≤ b and b ≤ c imply a ≤ c
smul_eq_mul
scalar multiplication of a natural number by a scalar is standard multiplication

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem simple_graph_local_avg_dominating_order_le_of_no_isolated {V : Type*} [Fintype V]    [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hiso : ∀ w, 0 < G.degree w)    (v : V) :    simple_graph_local_avg_dominating_order G v ≤      (5 * (Fintype.card V : ℚ) - 2 * G.degree v + 1) / 6 := by  classical  set D := simple_graph_dominating_sets_containing G v with hD  set n := Fintype.card V with hn  have memD : ∀ S, S ∈ D ↔ v ∈ S ∧ ∀ w, w ∈ S ∨ ∃ u ∈ S, G.Adj u w := by    intro S; rw [hD]; unfold simple_graph_dominating_sets_containing; simp  -- `D` is closed under supersets  have hup : ∀ S ∈ D, ∀ T, S ⊆ T → T ∈ D := by    intro S hS T hST    rw [memD] at hS ⊢    refine ⟨hST hS.1, fun w => ?_⟩    rcases hS.2 w with h | ⟨u, hu, h⟩    · exact Or.inl (hST h)    · exact Or.inr ⟨u, hST hu, h⟩  have hDne : D.Nonempty :=    ⟨Finset.univ, (memD _).2 ⟨Finset.mem_univ v, fun w => Or.inl (Finset.mem_univ w)⟩⟩  -- closed neighbourhoods and the vertices outside `N[v]`  set N : V → Finset V := fun w => insert w (G.neighborFinset w) with hN  set U : Finset V := (Finset.univ.erase v) \ G.neighborFinset v with hU  have hUcard : U.card = n - 1 - G.degree v := by    rw [hU, Finset.card_sdiff_of_subset, Finset.card_erase_of_mem (Finset.mem_univ v),      G.card_neighborFinset_eq_degree]    · rfl    · intro w hw      rw [Finset.mem_erase]      exact ⟨(G.ne_of_adj ((G.mem_neighborFinset v w).1 hw)).symm, Finset.mem_univ w⟩  have hdegle : G.degree v ≤ n - 1 := by    rw [← G.card_neighborFinset_eq_degree]    have : G.neighborFinset v ⊆ Finset.univ.erase v := by      intro w hw      rw [Finset.mem_erase]      exact ⟨(G.ne_of_adj ((G.mem_neighborFinset v w).1 hw)).symm, Finset.mem_univ w⟩    calc (G.neighborFinset v).card ≤ (Finset.univ.erase v).card := Finset.card_le_card this      _ = n - 1 := by rw [Finset.card_erase_of_mem (Finset.mem_univ v)]; rfl  have hn1 : 1 ≤ n := Fintype.card_pos_iff.2 ⟨v⟩  -- counts: `a x` sets containing `x`, `b x` avoiding `x`, `c x` sets in which `x` is critical  set a : V → ℕ := fun x => (D.filter (fun S => x ∈ S)).card with ha  set b : V → ℕ := fun x => (D.filter (fun S => x ∉ S)).card with hb  set c : V → ℕ := fun x => (D.filter (fun S => x ∈ S ∧ S.erase x ∉ D)).card with hc  have hab : ∀ x, a x + b x = D.card := fun x => Finset.card_filter_add_card_filter_not _  have habc : ∀ x, a x = b x + c x := by    intro x    simp only [ha, hb, hc]    have hsplit : (D.filter (fun S => x ∈ S)).card =        ((D.filter (fun S => x ∈ S)).filter (fun S => S.erase x ∈ D)).card +        ((D.filter (fun S => x ∈ S)).filter (fun S => ¬ S.erase x ∈ D)).card :=      (Finset.card_filter_add_card_filter_not _).symm    rw [Finset.filter_filter, Finset.filter_filter] at hsplit    rw [hsplit]    congr 1    -- erasing `x` matches the sets with `x` removable with the sets avoiding `x`    apply le_antisymm    · have inj : Set.InjOn (fun S : Finset V => S.erase x)          ↑(D.filter (fun S => x ∈ S ∧ S.erase x ∈ D)) := by        intro S hS T hT h        simp only [Finset.mem_coe, Finset.mem_filter] at hS hT        rw [← Finset.insert_erase hS.2.1, ← Finset.insert_erase hT.2.1]        exact congrArg (insert x) h      rw [← Finset.card_image_of_injOn inj]      apply Finset.card_le_card      intro T hT      obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT      simp only [Finset.mem_filter] at hS ⊢      exact ⟨hS.2.2, by simp⟩    · have inj : Set.InjOn (fun S : Finset V => insert x S) ↑(D.filter (fun S => x ∉ S)) := by        intro S hS T hT h        simp only [Finset.mem_coe, Finset.mem_filter] at hS hT        rw [← Finset.erase_insert hS.2, ← Finset.erase_insert hT.2]        exact congrArg (fun W => Finset.erase W x) h      rw [← Finset.card_image_of_injOn inj]      apply Finset.card_le_card      intro T hT      obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT      simp only [Finset.mem_filter] at hS ⊢      refine ⟨hup S hS.1 _ (Finset.subset_insert x S), Finset.mem_insert_self x S, ?_⟩      rw [Finset.erase_insert hS.2]; exact hS.1  have hsum : ∑ S ∈ D, S.card = ∑ x, a x := by    have h : ∀ S ∈ D, S.card = ∑ x, if x ∈ S then 1 else 0 := by      intro S _      rw [← Finset.card_filter, Finset.filter_mem_eq_inter, Finset.univ_inter]    rw [Finset.sum_congr rfl h, Finset.sum_comm]    refine Finset.sum_congr rfl fun x _ => ?_    simp only [ha]; rw [Finset.card_filter]  -- `x ≠ v` critical in `S`: `S` meets some `N[w]`, `w ∉ N[v]`, exactly in `x`  set E : V → V → Finset (Finset V) := fun w x => D.filter (fun S => S ∩ N w = {x}) with hE  have hcrit : ∀ x, x ≠ v → c x ≤ ∑ w ∈ U, (E w x).card := by    intro x hxv    simp only [hc]    refine le_trans (Finset.card_le_card ?_) Finset.card_biUnion_le    intro S hS    rw [Finset.mem_filter] at hS    obtain ⟨hSD, hxS, hSx⟩ := hS    have hvS : v ∈ S.erase x := Finset.mem_erase.2 ⟨hxv.symm, ((memD S).1 hSD).1⟩    rw [memD] at hSx    push_neg at hSx    obtain ⟨w, hwS, hwadj⟩ := hSx hvS    have hNw : S ∩ N w = {x} := by      ext y      simp only [Finset.mem_inter, hN, Finset.mem_insert, G.mem_neighborFinset,        Finset.mem_singleton]      constructor      · rintro ⟨hyS, hy⟩        by_contra hyx        have hy' : y ∈ S.erase x := Finset.mem_erase.2 ⟨hyx, hyS⟩        rcases hy with rfl | hy        · exact hwS hy'        · exact hwadj y hy' hy.symm      · intro hyx        rw [hyx]        refine ⟨hxS, ?_⟩        rcases ((memD S).1 hSD).2 w with h | ⟨u, hu, h⟩        · left          by_contra hne          exact hwS (Finset.mem_erase.2 ⟨fun h' => hne h'.symm, h⟩)        · right          by_cases hux : u = x          · rw [← hux]; exact h.symm          · exact absurd h (hwadj u (Finset.mem_erase.2 ⟨hux, hu⟩))    have hwU : w ∈ U := by      rw [hU, Finset.mem_sdiff, Finset.mem_erase, G.mem_neighborFinset]      refine ⟨⟨fun h => hwS (h ▸ hvS), Finset.mem_univ w⟩, fun h => hwadj v hvS h⟩    exact Finset.mem_biUnion.2 ⟨w, hwU, Finset.mem_filter.2 ⟨hSD, hNw⟩⟩  -- at most two thirds of the sets meet `N[w]` in a single vertex  have hthird : ∀ w, 3 * (D.filter (fun S => (S ∩ N w).card = 1)).card ≤ 2 * D.card := by    intro w    obtain ⟨w', hw'⟩ : ∃ w', G.Adj w w' := by      have := hiso w      rw [← G.card_neighborFinset_eq_degree, Finset.card_pos] at this      obtain ⟨w', hw'⟩ := this      exact ⟨w', (G.mem_neighborFinset w w').1 hw'⟩    have hww' : w ≠ w' := G.ne_of_adj hw'    have hwN : w ∈ N w := by simp [hN]    have hw'N : w' ∈ N w := by simp [hN, G.mem_neighborFinset, hw']    set single := D.filter (fun S => (S ∩ N w).card = 1) with hsingle    set multi := D.filter (fun S => ¬ (S ∩ N w).card = 1) with hmulti    have hsm : single.card + multi.card = D.card := Finset.card_filter_add_card_filter_not _    let φ : Finset V → Finset V := fun S => if w ∈ S then insert w' S else insert w S    have hmaps : ∀ S ∈ single, φ S ∈ multi := by      intro S hS      rw [hsingle, Finset.mem_filter, Finset.card_eq_one] at hS      obtain ⟨hSD, z, hz⟩ := hS      rw [hmulti, Finset.mem_filter]      by_cases hwS : w ∈ S      · simp only [φ, if_pos hwS]        refine ⟨hup S hSD _ (Finset.subset_insert _ _), fun h1 => ?_⟩        have hw_in : w ∈ insert w' S ∩ N w := Finset.mem_inter.2 ⟨Finset.mem_insert_of_mem hwS, hwN⟩        have hw'_in : w' ∈ insert w' S ∩ N w := Finset.mem_inter.2 ⟨Finset.mem_insert_self _ _, hw'N⟩        exact hww' (Finset.card_le_one.1 h1.le w hw_in w' hw'_in)      · simp only [φ, if_neg hwS]        refine ⟨hup S hSD _ (Finset.subset_insert _ _), fun h1 => ?_⟩        have hz_in : z ∈ S ∩ N w := by rw [hz]; exact Finset.mem_singleton_self z        have hzw : z ≠ w := fun h => hwS (h ▸ (Finset.mem_inter.1 hz_in).1)        have hw_in : w ∈ insert w S ∩ N w := Finset.mem_inter.2 ⟨Finset.mem_insert_self _ _, hwN⟩        have hz_in' : z ∈ insert w S ∩ N w :=          Finset.mem_inter.2 ⟨Finset.mem_insert_of_mem (Finset.mem_inter.1 hz_in).1,            (Finset.mem_inter.1 hz_in).2⟩        exact hzw (Finset.card_le_one.1 h1.le z hz_in' w hw_in)    have hfib : ∀ M, (single.filter (fun S => φ S = M)).card ≤ 2 := by      intro M      refine le_trans (Finset.card_le_card (t := {M.erase w', M.erase w}) ?_) Finset.card_le_two      intro S hS      rw [Finset.mem_filter, hsingle, Finset.mem_filter, Finset.card_eq_one] at hS      obtain ⟨⟨_, z, hz⟩, hφ⟩ := hS      rw [Finset.mem_insert, Finset.mem_singleton]      by_cases hwS : w ∈ S      · left        simp only [φ, if_pos hwS] at hφ        have hw'S : w' ∉ S := by          intro h          have h1 : w ∈ S ∩ N w := Finset.mem_inter.2 ⟨hwS, hwN⟩          have h2 : w' ∈ S ∩ N w := Finset.mem_inter.2 ⟨h, hw'N⟩          rw [hz, Finset.mem_singleton] at h1 h2          exact hww' (h1.trans h2.symm)        rw [← hφ, Finset.erase_insert hw'S]      · right        simp only [φ, if_neg hwS] at hφ        rw [← hφ, Finset.erase_insert hwS]    have hle2 : single.card ≤ 2 * multi.card :=      Finset.card_le_mul_card_image_of_maps_to hmaps 2 (fun M _ => hfib M)    omega  have hEsum : ∀ w, ∑ x ∈ Finset.univ.erase v, (E w x).card ≤      (D.filter (fun S => (S ∩ N w).card = 1)).card := by    intro w    rw [← Finset.card_biUnion]    · apply Finset.card_le_card      intro S hS      obtain ⟨x, -, hx⟩ := Finset.mem_biUnion.1 hS      rw [hE, Finset.mem_filter] at hx      rw [Finset.mem_filter, hx.2, Finset.card_singleton]      exact ⟨hx.1, rfl⟩    · intro x _ y _ hxy      rw [Function.onFun, Finset.disjoint_left]      intro S hSx hSy      rw [hE, Finset.mem_filter] at hSx hSy      exact hxy (Finset.singleton_injective (hSx.2.symm.trans hSy.2))  have hcsum : 3 * ∑ x, c x ≤ 3 * D.card + 2 * U.card * D.card := by    rw [← Finset.add_sum_erase _ _ (Finset.mem_univ v)]    have hcv : c v ≤ D.card := Finset.card_filter_le _ _    have h1 : ∑ x ∈ Finset.univ.erase v, c x ≤ ∑ w ∈ U, (D.filter (fun S => (S ∩ N w).card = 1)).card := by      calc ∑ x ∈ Finset.univ.erase v, c x          ≤ ∑ x ∈ Finset.univ.erase v, ∑ w ∈ U, (E w x).card :=            Finset.sum_le_sum fun x hx => hcrit x (Finset.ne_of_mem_erase hx)        _ = ∑ w ∈ U, ∑ x ∈ Finset.univ.erase v, (E w x).card := Finset.sum_comm        _ ≤ _ := Finset.sum_le_sum fun w _ => hEsum w    have h2 : 3 * ∑ w ∈ U, (D.filter (fun S => (S ∩ N w).card = 1)).card ≤ 2 * U.card * D.card := by      rw [Finset.mul_sum]      calc ∑ w ∈ U, 3 * (D.filter (fun S => (S ∩ N w).card = 1)).card          ≤ ∑ w ∈ U, 2 * D.card := Finset.sum_le_sum fun w _ => hthird w        _ = 2 * U.card * D.card := by rw [Finset.sum_const, smul_eq_mul]; ring    omega  have h2a : 2 * ∑ x, a x = n * D.card + ∑ x, c x := by    have e1 : ∑ x, (a x + b x) = n * D.card := by      rw [Finset.sum_congr rfl fun x _ => hab x, Finset.sum_const, smul_eq_mul, Finset.card_univ]    have e2 : ∑ x, a x = ∑ x, b x + ∑ x, c x := by      rw [← Finset.sum_add_distrib]; exact Finset.sum_congr rfl fun x _ => habc x    rw [← e1, Finset.sum_add_distrib]; omega  -- conclude  have hm : U.card + G.degree v + 1 = n := by rw [hUcard]; omega  have hDpos : (0 : ℚ) < D.card := by exact_mod_cast hDne.card_pos  have qa : (2 : ℚ) * ((∑ x, a x : ℕ) : ℚ) = n * D.card + ((∑ x, c x : ℕ) : ℚ) := by    exact_mod_cast h2a  have qc : (3 : ℚ) * ((∑ x, c x : ℕ) : ℚ) ≤ 3 * D.card + 2 * U.card * D.card := by    exact_mod_cast hcsum  have qm : (U.card : ℚ) + G.degree v + 1 = n := by exact_mod_cast hm  have qs : ∑ S ∈ D, (S.card : ℚ) = ((∑ x, a x : ℕ) : ℚ) := by rw [← hsum, Nat.cast_sum]  have qnD : (n : ℚ) * D.card = U.card * D.card + G.degree v * D.card + D.card := by    rw [← qm]; ring  unfold simple_graph_local_avg_dominating_order  rw [← hD, div_le_div_iff₀ hDpos (by norm_num : (0 : ℚ) < 6), qs]  linarith
See it in the graphDiscuss this resultChallenge it