AFTD Auto-Formalizing Theoretical Domains

digraph_abs_net_degree_le_third_of_indegree_lt

theoremverified

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

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.

  1. 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.

    lines 10–12

    uses digraph_outdegree_three_mul_le_edge_count

      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
  2. 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.

    lines 13–15

      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
  3. 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.

    lines 16–17

    uses abs_le

      rw [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

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
See it in the graphDiscuss this resultChallenge it