AFTD Auto-Formalizing Theoretical Domains

digraph_apex_over_bidirected_complete_out_degree

theoremverified

Every vertex of D_d has outdegree at least d.

Statement

theorem digraph_apex_over_bidirected_complete_out_degree (d : ℕ)
    [DecidableRel (digraph_apex_over_bidirected_complete d).Adj] (v : Fin (d + 2)) :
    d ≤ (Finset.univ.filter ((digraph_apex_over_bidirected_complete d).Adj v)).card
Source
Lemma for digraph_min_cut_additive_bound_fails_for_every_d; arXiv:2610.21381 (Optimally large cuts in both directions), Sec. 6.
Verified
16 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

To show that every vertex v has out-degree at least d, the proof exhibits an explicit subset of out-neighbors: all vertices other than v itself and the apex vertex Fin.last (d + 1). By definition of the digraph, v has directed edges to all such vertices. Since the total vertex set Fin (d + 2) has size d + 2, removing two vertices leaves at least (d + 2) - 2 = d vertices, giving the lower bound.

  1. Any vertex distinct from v and Fin.last (d + 1) is an out-neighbor of v, so (Finset.univ.erase v).erase (Fin.last (d + 1)) ⊆ Finset.univ.filter ((digraph_apex_over_bidirected_complete d).Adj v).

    Let w be any vertex in Finset.univ with v and Fin.last (d + 1) removed (introduced by `intro w hw`). By definition of finset erasure, w ≠ Fin.last (d + 1) and w ≠ v (via Finset.mem_erase, Finset.mem_univ, and_true). In this digraph, an edge from v to w exists if and only if v ≠ w and w ≠ Fin.last (d + 1) (via Finset.mem_filter, Finset.mem_univ, true_and). Since w ≠ v implies v ≠ w, both adjacency conditions hold, proving the inclusion.

    lines 4–9

    uses Finset.mem_erase, Finset.mem_univ, and_true, Finset.mem_filter, true_and

      have hsub : (Finset.univ.erase v).erase (Fin.last (d + 1)) ⊆
          Finset.univ.filter ((digraph_apex_over_bidirected_complete d).Adj v) := by
        intro w hw
        simp only [Finset.mem_erase, Finset.mem_univ, and_true] at hw
        simp only [Finset.mem_filter, Finset.mem_univ, true_and]
        exact ⟨fun h => hw.2 h.symm, hw.1⟩
  2. It suffices to show that the subset (Finset.univ.erase v).erase (Fin.last (d + 1)) has cardinality at least d.

    By monotonicity of cardinality on subsets (Finset.card_le_card) and transitivity of inequality (le_trans), the out-degree of v is at least the size of this subset. Hence, establishing d ≤ |(Finset.univ.erase v).erase (Fin.last (d + 1))| suffices.

    line 10

    uses le_trans, Finset.card_le_card

      refine le_trans ?_ (Finset.card_le_card hsub)
  3. The cardinality of (Finset.univ.erase v).erase (Fin.last (d + 1)) is at least d.

    Removing an element from a finset decreases its cardinality by at most 1 (Finset.pred_card_le_card_erase). Because v ∈ Finset.univ (Finset.mem_univ), removing v from the universe of Fin (d + 2) leaves exactly (d + 2) - 1 vertices (Finset.card_erase_of_mem, Finset.card_univ, Fintype.card_fin). Erasing Fin.last (d + 1) then leaves at least (d + 2) - 1 - 1 vertices, which linear arithmetic (omega) simplifies to d.

    lines 11–13

    uses Finset.pred_card_le_card_erase, Finset.card_erase_of_mem, Finset.mem_univ, Finset.card_univ, Fintype.card_fin

      have h1 := Finset.pred_card_le_card_erase (s := Finset.univ.erase v) (a := Fin.last (d + 1))
      rw [Finset.card_erase_of_mem (Finset.mem_univ v), Finset.card_univ, Fintype.card_fin] at h1
      omega
Finset.mem_erase
An element a belongs to s.erase b if and only if a ≠ b and a ∈ s.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
and_true
For any proposition p, the conjunction p ∧ True simplifies to p.
Finset.mem_filter
An element a belongs to Finset.filter p s if and only if a ∈ s and p a holds.
true_and
For any proposition p, the conjunction True ∧ p simplifies to p.
le_trans
If a ≤ b and b ≤ c, then a ≤ c.
Finset.card_le_card
If s ⊆ t, then |s| ≤ |t|.
Finset.pred_card_le_card_erase
Removing an element from a finset decreases its cardinality by at most 1: |s| - 1 ≤ |s.erase a|.
Finset.card_erase_of_mem
Removing an element a that belongs to s decreases its cardinality by exactly 1: |s.erase a| = |s| - 1.
Finset.card_univ
The cardinality of the universal finset of a type α equals the cardinality of α.
Fintype.card_fin
The cardinality of Fin n is n.

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_apex_over_bidirected_complete_out_degree (d : ℕ)    [DecidableRel (digraph_apex_over_bidirected_complete d).Adj] (v : Fin (d + 2)) :    d ≤ (Finset.univ.filter ((digraph_apex_over_bidirected_complete d).Adj v)).card := by  have hsub : (Finset.univ.erase v).erase (Fin.last (d + 1)) ⊆      Finset.univ.filter ((digraph_apex_over_bidirected_complete d).Adj v) := by    intro w hw    simp only [Finset.mem_erase, Finset.mem_univ, and_true] at hw    simp only [Finset.mem_filter, Finset.mem_univ, true_and]    exact ⟨fun h => hw.2 h.symm, hw.1⟩  refine le_trans ?_ (Finset.card_le_card hsub)  have h1 := Finset.pred_card_le_card_erase (s := Finset.univ.erase v) (a := Fin.last (d + 1))  rw [Finset.card_erase_of_mem (Finset.mem_univ v), Finset.card_univ, Fintype.card_fin] at h1  omega
See it in the graphDiscuss this resultChallenge it