digraph_apex_over_bidirected_complete_three_max_min_cut
For d = 3 (m = 16 arcs), every bipartition of D_3 has a directed cut of size at most 4 = ⌈2m/10⌉, so the bound of Conjecture 6.1 of arXiv:2610.21381 is attained at m = 16.
Statement
theorem digraph_apex_over_bidirected_complete_three_max_min_cut
[DecidableRel (digraph_apex_over_bidirected_complete 3).Adj] :
(∀ A : Finset (Fin 5), min (digraph_cut_count (digraph_apex_over_bidirected_complete 3) A Aᶜ)
(digraph_cut_count (digraph_apex_over_bidirected_complete 3) Aᶜ A) ≤ 4) ∧
digraph_edge_count (digraph_apex_over_bidirected_complete 3) = 16- 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.
The proof, explained
The theorem asserts that the 5-vertex directed graph $D_3$—an apex vertex with outgoing edges to a complete bidirected graph on 4 vertices—has 16 edges in total and every bipartition has a directed cut of size at most 4. Because the vertex set has only 5 vertices, there are only $2^5 = 32$ bipartitions to test. The proof replaces the abstract decidability hypothesis with Lean's canonical computable decider, unfolds the cut and edge count definitions, and finishes by exhaustive finite computation via `decide`.
The assumed decidability instance for graph adjacency is identified with the canonical computable decision procedure.
Because the decidability of any proposition is unique up to equality (a subsingleton), `Subsingleton.elim` shows that the abstract decidability instance assumed in the theorem hypothesis equals the canonical decision procedure for the concrete adjacency relation $u \ne v \land v \ne 4$. Substituting this equality replaces the abstract decider with the computable one throughout the goal.
uses
Subsingleton.elimhave e : ‹DecidableRel (digraph_apex_over_bidirected_complete 3).Adj› = fun u v => (inferInstance : Decidable (u ≠ v ∧ v ≠ Fin.last 4)) := Subsingleton.elim _ _ subst e
The cut size and edge count functions are expanded in terms of filtering sets of vertex pairs.
Unfolding the definitions of `digraph_cut_count` and `digraph_edge_count` rewrites the directed cuts as the cardinalities of adjacent pairs in $A \times A^c$ (and $A^c \times A$), and the edge count as the cardinality of all adjacent vertex pairs in $\text{Fin } 5 \times \text{Fin } 5$.
unfold digraph_cut_count digraph_edge_countFor every subset $A \subseteq \text{Fin } 5$, $\min(|E(A, A^c)|, |E(A^c, A)|) \le 4$, and the total edge count of $D_3$ is 16. automation
Because the vertex set $\text{Fin } 5$ contains only 5 vertices, there are only $2^5 = 32$ subsets $A$ to consider. The `decide` tactic exhaustively evaluates the inequality for all 32 bipartitions and counts the 16 edges by direct computation.
decide
Subsingleton.elim- Any two elements of a type that has at most one element (a subsingleton) are equal.
- The theorem assumes an arbitrary decidability instance for adjacency as a typeclass parameter. Lines 6–8 replace this abstract instance with Lean's canonical computable one; on paper, decidability for a finite graph is trivial and taken for granted.
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_three_max_min_cut [DecidableRel (digraph_apex_over_bidirected_complete 3).Adj] : (∀ A : Finset (Fin 5), min (digraph_cut_count (digraph_apex_over_bidirected_complete 3) A Aᶜ) (digraph_cut_count (digraph_apex_over_bidirected_complete 3) Aᶜ A) ≤ 4) ∧ digraph_edge_count (digraph_apex_over_bidirected_complete 3) = 16 := by have e : ‹DecidableRel (digraph_apex_over_bidirected_complete 3).Adj› = fun u v => (inferInstance : Decidable (u ≠ v ∧ v ≠ Fin.last 4)) := Subsingleton.elim _ _ subst e unfold digraph_cut_count digraph_edge_count decide