AFTD Auto-Formalizing Theoretical Domains

digraph_weighted_in_degree_below_half

theoremverified

In a finite nonempty oriented graph, some vertex minimizes the weight of its in-neighborhood, and that in-neighborhood has at most half the total nonnegative integer weight.

Statement

theorem digraph_weighted_in_degree_below_half
    {α : Type} [Fintype α] [DecidableEq α] [Nonempty α]
    (D : Digraph α) [DecidableRel D.Adj]
    (horient : ∀ u v, D.Adj u v → ¬ D.Adj v u) (w : α → ℕ) :
    ∃ v, (∀ x, (∑ u ∈ Finset.univ.filter (fun u => D.Adj u v), w u) ≤
      ∑ u ∈ Finset.univ.filter (fun u => D.Adj u x), w u) ∧
      2 * (∑ u ∈ Finset.univ.filter (fun u => D.Adj u v), w u) ≤
        ∑ u ∈ Finset.univ, w u
Source
Elementary weighted averaging over oriented vertex pairs; no novelty is claimed.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

The proof, explained

The proof selects a vertex s that minimizes the weighted in-degree (score) among all vertices. By double-counting the edge-weight sum ∑_{u, v} F(u, v) where F(u, v) = w(u)w(v) for directed edges u → v, and using the orientation condition that prevents both (u, v) and (v, u) from coexisting, the weighted sum of all scores is bounded by W²/2, where W is the total vertex weight. Averaging then gives W * score(s) ≤ ∑_v w(v) score(v) ≤ W²/2, which implies 2 * score(s) ≤ W upon dividing by W (with W = 0 treated as a simple base case).

  1. Define total weight W, the score function, and select a vertex s minimizing score.

    We define the total weight W = ∑ u, w u, the score of any vertex v as its weighted in-degree ∑_{u → v} w u, and an auxiliary function F u v = w u * w v if u → v and 0 otherwise. Since the vertex set is finite and nonempty, we choose a vertex s that minimizes the score.

    lines 9–13

    uses Finset.exists_min_image, Finset.univ_nonempty

      classical
      let W : ℕ := ∑ u, w u
      let score : α → ℕ := fun v => ∑ u ∈ Finset.univ.filter (fun u => D.Adj u v), w u
      let F : α → α → ℕ := fun u v => if D.Adj u v then w u * w v else 0
      obtain ⟨s, hs, hmin⟩ := Finset.exists_min_image Finset.univ score Finset.univ_nonempty
  2. For all vertices u and v, F u v + F v u ≤ w u * w v.

    Because the digraph is oriented, it cannot contain both edges (u, v) and (v, u). Case analysis shows: if u → v, then v ↛ u, giving w u * w v + 0 ≤ w u * w v; if v → u, then 0 + w v * w u = w u * w v; and if neither edge is present, 0 + 0 ≤ w u * w v.

    lines 14–21

    uses Nat.mul_comm

      have hpair : ∀ u v, F u v + F v u ≤ w u * w v := by
        intro u v
        by_cases huv : D.Adj u v
        · have hvu := horient u v huv
          simp [F, huv, hvu]
        · by_cases hvu : D.Adj v u
          · simp [F, huv, hvu, Nat.mul_comm]
          · simp [F, huv, hvu]
  3. ∑ u, ∑ v, (F u v + F v u) ≤ ∑ u, ∑ v, w u * w v.

    Summing the pairwise inequality F u v + F v u ≤ w u * w v over all pairs of vertices u and v preserves the inequality by monotonicity of finite sums.

    lines 22–28

    uses Finset.sum_le_sum

      have hdouble : (∑ u, ∑ v, (F u v + F v u)) ≤
          ∑ u, ∑ v, w u * w v := by
        apply Finset.sum_le_sum
        intro u _
        apply Finset.sum_le_sum
        intro v _
        exact hpair u v
  4. ∑ u, ∑ v, F v u = ∑ u, ∑ v, F u v.

    Exchanging the two summation indices shows that the double sum of F v u equals the double sum of F u v.

    lines 29–30

    uses Finset.sum_comm

      have hsym : (∑ u, ∑ v, F v u) = ∑ u, ∑ v, F u v := by
        exact Finset.sum_comm
  5. ∑ u, ∑ v, w u * w v = W * W.

    Distributing multiplication over addition factors the double sum into (∑ u, w u) * (∑ v, w v), which equals W * W by definition of W.

    lines 31–34

    uses Finset.sum_mul, Finset.mul_sum

      have hprod : (∑ u, ∑ v, w u * w v) = W * W := by
        dsimp [W]
        rw [Finset.sum_mul]
        simp only [Finset.mul_sum]
  6. ∑ u, ∑ v, F u v = ∑ v, w v * score v.

    Swapping the order of summation gives ∑ v, ∑ u, F u v. For each fixed v, the inner sum over u is supported only on vertices u with u → v, where F u v = w u * w v. Factoring out w v leaves w v * ∑_{u → v} w u = w v * score v.

    lines 35–39

    uses Finset.sum_comm, Finset.sum_congr, Finset.mul_sum, Finset.sum_filter, Nat.mul_comm

      have hF : (∑ u, ∑ v, F u v) = ∑ v, w v * score v := by
        rw [Finset.sum_comm]
        apply Finset.sum_congr rfl
        intro v _
        simp [F, score, Finset.mul_sum, Finset.sum_filter, Nat.mul_comm]
  7. 2 * (∑ v, w v * score v) ≤ W * W.

    Distributing the double sum of F u v + F v u into two identical sums of ∑ v, w v * score v and substituting W * W on the right-hand side yields 2 * (∑ v, w v * score v) ≤ W * W.

    lines 40–44

    uses Finset.sum_add_distrib

      have hbound : 2 * (∑ v, w v * score v) ≤ W * W := by
        simp only [Finset.sum_add_distrib] at hdouble
        rw [hsym, hprod] at hdouble
        simp only [hF] at hdouble
        omega
  8. W * score s ≤ ∑ v, w v * score v.

    Because s minimizes the score, score s ≤ score v holds for every vertex v. Multiplying by w v and summing over all v gives (∑ v, w v) * score s = W * score s ≤ ∑ v, w v * score v.

    lines 45–51

    uses Finset.sum_mul, Finset.sum_le_sum, Nat.mul_le_mul_left

      have hminsum : W * score s ≤ ∑ v, w v * score v := by
        calc
          W * score s = ∑ v, w v * score s := by simp [W, Finset.sum_mul]
          _ ≤ ∑ v, w v * score v := by
            apply Finset.sum_le_sum
            intro v hv
            exact Nat.mul_le_mul_left _ (hmin v hv)
  9. If W = 0, the minimal vertex s satisfies the theorem.

    When W = 0, the in-degree score of s is at most the total weight W, so score s = 0. Thus 2 * score s ≤ W holds trivially, and s minimizes the score by construction.

    lines 52–60

    uses Finset.mem_univ, Finset.sum_le_sum_of_subset, Finset.filter_subset

      by_cases hW : W = 0
      · refine ⟨s, ?_, ?_⟩
        · intro x
          exact hmin x (Finset.mem_univ x)
        · have hscore : score s ≤ W := by
            simpa [score, W] using
              (Finset.sum_le_sum_of_subset (f := w) (Finset.filter_subset (fun u => D.Adj u s) Finset.univ))
          have : 2 * score s ≤ W := by omega
          simpa [score, W] using this
  10. If W > 0, the minimal vertex s satisfies the theorem.

    Chaining the inequalities gives W * (2 * score s) = 2 * (W * score s) ≤ 2 * (∑ v, w v * score v) ≤ W * W. Because W > 0, dividing both sides by W yields 2 * score s ≤ W. Combined with the minimality of score s, this finishes the proof.

    lines 61–67

    uses Nat.pos_of_ne_zero, Nat.le_of_mul_le_mul_left, Finset.mem_univ

      · have hWpos : 0 < W := Nat.pos_of_ne_zero hW
        have hkey : W * (2 * score s) ≤ W * W := by nlinarith
        have hscore : 2 * score s ≤ W := Nat.le_of_mul_le_mul_left hkey hWpos
        refine ⟨s, ?_, ?_⟩
        · intro x
          exact hmin x (Finset.mem_univ x)
        · simpa [score, W] using hscore
Finset.exists_min_image
A nonempty finite set contains an element that minimizes a given function.
Finset.univ_nonempty
The universal finset of a nonempty finite type is nonempty.
Nat.mul_comm
Multiplication of natural numbers is commutative.
Finset.sum_le_sum
If an inequality between two functions holds pointwise over a finite set, it holds between their sums.
Finset.sum_comm
The order of summation in a finite double sum can be swapped.
Finset.sum_mul
Multiplication by a scalar on the right distributes over finite sums.
Finset.mul_sum
Multiplication by a scalar on the left distributes over finite sums.
Finset.sum_congr
Two sums over the same finite set are equal if their terms agree at every element.
Finset.sum_filter
Summing over a filtered subset equals summing an if-then-else indicator over the whole set.
Finset.sum_add_distrib
The sum of a pointwise sum of two functions over a finite set is the sum of their individual sums.
Nat.mul_le_mul_left
Multiplying both sides of an inequality of natural numbers on the left by a constant preserves the inequality.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
Finset.sum_le_sum_of_subset
Summing a nonnegative function over a subset of a finite set is at most the sum over the entire set.
Finset.filter_subset
Filtering a finite set by a predicate produces a subset of that set.
Nat.pos_of_ne_zero
A nonzero natural number is strictly positive.
Nat.le_of_mul_le_mul_left
If c * a ≤ c * b for natural numbers with c > 0, then a ≤ b.

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 digraph_weighted_in_degree_below_half    {α : Type} [Fintype α] [DecidableEq α] [Nonempty α]    (D : Digraph α) [DecidableRel D.Adj]    (horient : ∀ u v, D.Adj u v → ¬ D.Adj v u) (w : α → ℕ) :    ∃ v, (∀ x, (∑ u ∈ Finset.univ.filter (fun u => D.Adj u v), w u) ≤      ∑ u ∈ Finset.univ.filter (fun u => D.Adj u x), w u) ∧      2 * (∑ u ∈ Finset.univ.filter (fun u => D.Adj u v), w u) ≤        ∑ u ∈ Finset.univ, w u := by  classical  let W : ℕ := ∑ u, w u  let score : α → ℕ := fun v => ∑ u ∈ Finset.univ.filter (fun u => D.Adj u v), w u  let F : α → α → ℕ := fun u v => if D.Adj u v then w u * w v else 0  obtain ⟨s, hs, hmin⟩ := Finset.exists_min_image Finset.univ score Finset.univ_nonempty  have hpair : ∀ u v, F u v + F v u ≤ w u * w v := by    intro u v    by_cases huv : D.Adj u v    · have hvu := horient u v huv      simp [F, huv, hvu]    · by_cases hvu : D.Adj v u      · simp [F, huv, hvu, Nat.mul_comm]      · simp [F, huv, hvu]  have hdouble : (∑ u, ∑ v, (F u v + F v u)) ≤      ∑ u, ∑ v, w u * w v := by    apply Finset.sum_le_sum    intro u _    apply Finset.sum_le_sum    intro v _    exact hpair u v  have hsym : (∑ u, ∑ v, F v u) = ∑ u, ∑ v, F u v := by    exact Finset.sum_comm  have hprod : (∑ u, ∑ v, w u * w v) = W * W := by    dsimp [W]    rw [Finset.sum_mul]    simp only [Finset.mul_sum]  have hF : (∑ u, ∑ v, F u v) = ∑ v, w v * score v := by    rw [Finset.sum_comm]    apply Finset.sum_congr rfl    intro v _    simp [F, score, Finset.mul_sum, Finset.sum_filter, Nat.mul_comm]  have hbound : 2 * (∑ v, w v * score v) ≤ W * W := by    simp only [Finset.sum_add_distrib] at hdouble    rw [hsym, hprod] at hdouble    simp only [hF] at hdouble    omega  have hminsum : W * score s ≤ ∑ v, w v * score v := by    calc      W * score s = ∑ v, w v * score s := by simp [W, Finset.sum_mul]      _ ≤ ∑ v, w v * score v := by        apply Finset.sum_le_sum        intro v hv        exact Nat.mul_le_mul_left _ (hmin v hv)  by_cases hW : W = 0  · refine ⟨s, ?_, ?_⟩    · intro x      exact hmin x (Finset.mem_univ x)    · have hscore : score s ≤ W := by        simpa [score, W] using          (Finset.sum_le_sum_of_subset (f := w) (Finset.filter_subset (fun u => D.Adj u s) Finset.univ))      have : 2 * score s ≤ W := by omega      simpa [score, W] using this  · have hWpos : 0 < W := Nat.pos_of_ne_zero hW    have hkey : W * (2 * score s) ≤ W * W := by nlinarith    have hscore : 2 * score s ≤ W := Nat.le_of_mul_le_mul_left hkey hWpos    refine ⟨s, ?_, ?_⟩    · intro x      exact hmin x (Finset.mem_univ x)    · simpa [score, W] using hscore
See it in the graphDiscuss this resultChallenge it