digraph_abs_net_degree_le_third_of_indegree_lt
Under the low-indegree hypotheses of the target, every absolute net degree is at most one third of the total arc count.
Statement
theorem digraph_abs_net_degree_le_third_of_indegree_lt {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) (hin : ∀ v, ((Finset.univ.filter fun u => G.Adj u v).card : ℚ) < (digraph_edge_count G : ℚ) / 3 + 1) (v : V) : |((Finset.univ.filter (G.Adj v)).card : ℚ) - ((Finset.univ.filter fun u => G.Adj u v).card : ℚ)| ≤ (digraph_edge_count G : ℚ) / 3
- 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_outdegree_three_mul_le_edge_countIn a finite loopless digraph of minimum outdegree at least two, three times any vertex outdegree is at most the total number of arcs.
The proof, explained
The theorem establishes that the absolute net degree |d⁺(v) - d⁻(v)| at any vertex v is at most one third of the total edge count E. Rewriting the absolute value inequality via abs_le reduces the claim to verifying two linear inequalities: d⁻(v) - d⁺(v) ≤ E/3 and d⁺(v) - d⁻(v) ≤ E/3. The first inequality holds because the in-degree is strictly less than E/3 + 1 while the out-degree is at least 2. The second inequality holds because 3 d⁺(v) ≤ E by an out-degree packing lemma and in-degrees are non-negative.
The out-degree of v satisfies 3 d⁺(v) ≤ E as a rational inequality, where E is the total edge count of G.
Applying the lemma digraph_outdegree_three_mul_le_edge_count to G with the loop-free and minimum out-degree hypotheses establishes 3 d⁺(v) ≤ E over ℕ. This inequality is then cast into the rational numbers.
uses
digraph_outdegree_three_mul_le_edge_counthave ho := digraph_outdegree_three_mul_le_edge_count G hloop hdeg v have ho' : 3 * ((Finset.univ.filter (G.Adj v)).card : ℚ) ≤ (digraph_edge_count G : ℚ) := by exact_mod_cast ho
The in-degree and out-degree of v satisfy d⁻(v) < E/3 + 1, d⁺(v) ≥ 2, and d⁻(v) ≥ 0 over the rationals.
Specializing the hypothesis hin to v gives the rational inequality d⁻(v) < E/3 + 1. Casting the minimum out-degree hypothesis hdeg to the rationals gives d⁺(v) ≥ 2, and the in-degree is non-negative because the cardinality of a finite set is non-negative.
have hi := hin v have hd : (2 : ℚ) ≤ (Finset.univ.filter (G.Adj v)).card := by exact_mod_cast hdeg v have hn : (0 : ℚ) ≤ (Finset.univ.filter fun u => G.Adj u v).card := by positivity
The absolute net degree |d⁺(v) - d⁻(v)| is at most E/3.
Rewriting with abs_le converts the absolute value inequality |d⁺(v) - d⁻(v)| ≤ E/3 into the conjunction -(E/3) ≤ d⁺(v) - d⁻(v) ∧ d⁺(v) - d⁻(v) ≤ E/3. Splitting into the two directional bounds, both are solved by linear rational arithmetic (linarith): the lower bound d⁻(v) - d⁺(v) ≤ E/3 follows from d⁻(v) < E/3 + 1 and d⁺(v) ≥ 2; the upper bound d⁺(v) - d⁻(v) ≤ E/3 follows from 3 d⁺(v) ≤ E and d⁻(v) ≥ 0.
uses
abs_lerw [abs_le] constructor <;> linarith
digraph_outdegree_three_mul_le_edge_count- In a loopless directed graph where every vertex has out-degree at least 2, three times the out-degree of any vertex is at most the total number of edges.
abs_le- In any linearly ordered additive commutative group, |a| ≤ b if and only if -b ≤ a and 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_abs_net_degree_le_third_of_indegree_lt {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) (hin : ∀ v, ((Finset.univ.filter fun u => G.Adj u v).card : ℚ) < (digraph_edge_count G : ℚ) / 3 + 1) (v : V) : |((Finset.univ.filter (G.Adj v)).card : ℚ) - ((Finset.univ.filter fun u => G.Adj u v).card : ℚ)| ≤ (digraph_edge_count G : ℚ) / 3 := by have ho := digraph_outdegree_three_mul_le_edge_count G hloop hdeg v have ho' : 3 * ((Finset.univ.filter (G.Adj v)).card : ℚ) ≤ (digraph_edge_count G : ℚ) := by exact_mod_cast ho have hi := hin v have hd : (2 : ℚ) ≤ (Finset.univ.filter (G.Adj v)).card := by exact_mod_cast hdeg v have hn : (0 : ℚ) ≤ (Finset.univ.filter fun u => G.Adj u v).card := by positivity rw [abs_le] constructor <;> linarith