digraph_weighted_in_degree_below_half
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
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).
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.
uses
Finset.exists_min_image,Finset.univ_nonemptyclassical 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
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.
uses
Nat.mul_commhave 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]
∑ 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.
uses
Finset.sum_le_sumhave 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
∑ 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.
uses
Finset.sum_commhave hsym : (∑ u, ∑ v, F v u) = ∑ u, ∑ v, F u v := by exact Finset.sum_comm
∑ 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.
uses
Finset.sum_mul,Finset.mul_sumhave hprod : (∑ u, ∑ v, w u * w v) = W * W := by dsimp [W] rw [Finset.sum_mul] simp only [Finset.mul_sum]
∑ 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.
uses
Finset.sum_comm,Finset.sum_congr,Finset.mul_sum,Finset.sum_filter,Nat.mul_commhave 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]
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.
uses
Finset.sum_add_distribhave 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
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.
uses
Finset.sum_mul,Finset.sum_le_sum,Nat.mul_le_mul_lefthave 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)
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.
uses
Finset.mem_univ,Finset.sum_le_sum_of_subset,Finset.filter_subsetby_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
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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem 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