digraph_outdegree_three_mul_le_edge_count
In a finite loopless digraph of minimum outdegree at least two, three times any vertex outdegree is at most the total number of arcs.
Statement
theorem digraph_outdegree_three_mul_le_edge_count {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (hloop : ∀ v, ¬ G.Adj v v) (hdeg : ∀ v, 2 ≤ (Finset.univ.filter (G.Adj v)).card) (v : V) : 3 * (Finset.univ.filter (G.Adj v)).card ≤ digraph_edge_count G
- Source
- Helper for digraph_both_cuts_ge_ceil_div_six_of_indegree_lt, arXiv:2610.21381, proof of Theorem 1.4, Case 2. The two-partition certificate and paired-outcome inequality are a deterministic formulation of the paper's averaging argument; no research advance is claimed.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- digraph_edge_countThe number m of edges (arcs) of a finite digraph G.
- digraph_edge_count_eq_sum_outdegreesThe number of arcs of a finite digraph equals the sum of its outdegrees.
- Used by 1
- digraph_abs_net_degree_le_third_of_indegree_ltUnder the low-indegree hypotheses of the target, every absolute net degree is at most one third of the total arc count.
The proof, explained
The total number of directed edges in G equals the sum of all vertex outdegrees, which splits into the outdegree d(v) of v plus the sum of outdegrees over all other vertices V \ {v}. Since G has no self-loops, all out-neighbors of v lie in V \ {v}, so d(v) ≤ |V \ {v}|. Every vertex has outdegree at least two, meaning the remaining vertices contribute at least 2 |V \ {v}| ≥ 2 d(v) edges, giving at least 2 d(v) + d(v) = 3 d(v) edges in total.
The outdegree of v is at most the number of other vertices in the digraph, |V \ {v}|.
Abbreviating the outdegree function as d(u), we observe that because G has no self-loops (hloop), v cannot be adjacent to itself. Every out-neighbor of v therefore belongs to V \ {v}. Since the out-neighborhood is a subset of V \ {v}, its cardinality d(v) is at most |V \ {v}| by Finset.card_le_card.
uses
Finset.card_le_card,Finset.mem_erase.mpr,Finset.mem_univ,Finset.mem_filter.mplet d : V → ℕ := fun u => (Finset.univ.filter (G.Adj u)).card have hd : d v ≤ (Finset.univ.erase v).card := by apply Finset.card_le_card intro u hu apply Finset.mem_erase.mpr refine ⟨?_, Finset.mem_univ u⟩ intro h subst u exact hloop v (Finset.mem_filter.mp hu).2
The sum of outdegrees of all vertices other than v is at least 2 |V \ {v}|.
By hypothesis hdeg, every vertex has outdegree at least 2. Summing this lower bound over all vertices in V \ {v} shows that the sum of outdegrees is at least the sum of 2 over V \ {v} (via Finset.sum_le_sum), which simplifies to 2 |V \ {v}|.
uses
Finset.sum_le_sumhave hother : (Finset.univ.erase v).card * 2 ≤ ∑ u ∈ Finset.univ.erase v, d u := by calc _ = ∑ _u ∈ Finset.univ.erase v, 2 := by simp _ ≤ _ := Finset.sum_le_sum (fun u _ => hdeg u)
The total edge count of G is the sum of outdegrees of all other vertices plus the outdegree of v.
Decomposing the sum of outdegrees over all vertices by separating the term for v (Finset.sum_erase_add) yields (∑_{u ≠ v} d(u)) + d(v) = ∑_{u} d(u). By digraph_edge_count_eq_sum_outdegrees, this total sum of outdegrees equals the total number of edges in G.
uses
Finset.sum_erase_add,Finset.mem_univ,digraph_edge_count_eq_sum_outdegreeshave hsplit : (∑ u ∈ Finset.univ.erase v, d u) + d v = digraph_edge_count G := by rw [Finset.sum_erase_add _ _ (Finset.mem_univ v)] exact (digraph_edge_count_eq_sum_outdegrees G).symm
Three times the outdegree of v is at most the total edge count of G.
We rewrite the goal as 3 * d(v) ≤ digraph_edge_count G. From the previous steps, the total edge count is (∑_{u ≠ v} d(u)) + d(v) ≥ 2 |V \ {v}| + d(v) ≥ 2 d(v) + d(v) = 3 d(v). Linear integer arithmetic (omega) finishes the proof.
change 3 * d v ≤ digraph_edge_count G omega
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to the other's cardinality.
Finset.mem_erase.mpr- An element belongs to a finite set with another element erased if it is distinct from that element and belongs to the original set.
Finset.mem_univ- Every element of a finite type belongs to its universal set.
Finset.mem_filter.mp- If an element belongs to a filtered set, then it belongs to the base set and satisfies the filtering predicate.
Finset.sum_le_sum- If a function is termwise bounded by another across a finite set, its sum over that set is bounded by the sum of the other.
Finset.sum_erase_add- The sum of a function over a set with an element removed, plus the value at that element, equals the sum over the whole set.
digraph_edge_count_eq_sum_outdegrees- In a finite digraph, the total number of directed edges equals the sum of the outdegrees of all vertices.
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_outdegree_three_mul_le_edge_count {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (hloop : ∀ v, ¬ G.Adj v v) (hdeg : ∀ v, 2 ≤ (Finset.univ.filter (G.Adj v)).card) (v : V) : 3 * (Finset.univ.filter (G.Adj v)).card ≤ digraph_edge_count G := by let d : V → ℕ := fun u => (Finset.univ.filter (G.Adj u)).card have hd : d v ≤ (Finset.univ.erase v).card := by apply Finset.card_le_card intro u hu apply Finset.mem_erase.mpr refine ⟨?_, Finset.mem_univ u⟩ intro h subst u exact hloop v (Finset.mem_filter.mp hu).2 have hother : (Finset.univ.erase v).card * 2 ≤ ∑ u ∈ Finset.univ.erase v, d u := by calc _ = ∑ _u ∈ Finset.univ.erase v, 2 := by simp _ ≤ _ := Finset.sum_le_sum (fun u _ => hdeg u) have hsplit : (∑ u ∈ Finset.univ.erase v, d u) + d v = digraph_edge_count G := by rw [Finset.sum_erase_add _ _ (Finset.mem_univ v)] exact (digraph_edge_count_eq_sum_outdegrees G).symm change 3 * d v ≤ digraph_edge_count G omega