AFTD Auto-Formalizing Theoretical Domains

digraph_outdegree_three_mul_le_edge_count

theoremverified

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
Used by 1

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.

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

    lines 6–14

    uses Finset.card_le_card, Finset.mem_erase.mpr, Finset.mem_univ, Finset.mem_filter.mp

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

    lines 15–18

    uses Finset.sum_le_sum

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

    lines 19–21

    uses Finset.sum_erase_add, Finset.mem_univ, digraph_edge_count_eq_sum_outdegrees

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

    lines 22–23

      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

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