digraph_apex_over_bidirected_complete_out_degree
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
- digraph_apex_over_bidirected_completeThe digraph D_d on d + 2 vertices: a bidirected complete graph on the vertices 0, …, d, together with an apex d + 1 that sends an arc to…
- digraph_cut_counte_G(A, B): the number of edges of the digraph G from a vertex of A to a vertex of B.
- digraph_edge_countThe number m of edges (arcs) of a finite digraph G.
- Used by 1
- digraph_min_cut_additive_bound_fails_for_every_dFor every d ≥ 2 there is a loopless digraph with minimum outdegree at least d and m = (d + 1)² arcs in which every vertex bipartition A ⊔…
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.
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.
uses
Finset.mem_erase,Finset.mem_univ,and_true,Finset.mem_filter,true_andhave 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⟩
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.
uses
le_trans,Finset.card_le_cardrefine le_trans ?_ (Finset.card_le_card hsub)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.
uses
Finset.pred_card_le_card_erase,Finset.card_erase_of_mem,Finset.mem_univ,Finset.card_univ,Fintype.card_finhave 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.
- The proof does not need to split cases on whether v is the apex Fin.last (d + 1): Finset.pred_card_le_card_erase bounds the drop in cardinality by 1 whether the element being removed was in the set or not, giving a uniform lower bound of (d + 2) - 1 - 1 = d in all cases.
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_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