digraph_apex_over_bidirected_complete_three_has_bipartition
There exists a vertex bipartition V = A ⊔ B of the apex digraph D₃ on 5 vertices such that both directed cut counts e(A, B) and e(B, A) are at least 4, attaining the bound ⌈(3 - 1) * 16 / (2 * (2 * 3 - 1))⌉ = 4 of Conjecture 6.1 of arXiv:2610.21381.
Statement
theorem digraph_apex_over_bidirected_complete_three_has_bipartition
[DecidableRel (digraph_apex_over_bidirected_complete 3).Adj] :
∃ A B : Finset (Fin 5), Disjoint A B ∧ A ∪ B = Finset.univ ∧
4 ≤ digraph_cut_count (digraph_apex_over_bidirected_complete 3) A B ∧
4 ≤ digraph_cut_count (digraph_apex_over_bidirected_complete 3) B A- Formalizes
- arXiv:2610.21381 Conjecture 6.1
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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.
Read back from the Lean
Assuming that the adjacency relation of digraph_apex_over_bidirected_complete 3 is decidable, there exist finite subsets $A$ and $B$ of Fin 5 such that:
1. $A$ and $B$ are disjoint,
2. $A \cup B$ is the universal set of Fin 5 (that is, $(A, B)$ partitions Fin 5),
3. The number of directed edges from $A$ to $B$ in digraph_apex_over_bidirected_complete 3 is at least 4, and
4. The number of directed edges from $B$ to $A$ in digraph_apex_over_bidirected_complete 3 is at least 4.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by exhibiting an explicit vertex bipartition of the 5-vertex apex digraph, namely A = {0, 1} and B = {2, 3, 4}. After standardizing the decidability instance to allow computation, the properties—disjointness, covering the entire vertex set, and attaining directed cut counts e(A, B) = 4 and e(B, A) = 6 (both at least 4)—are verified by finite exhaustive evaluation.
The assumed decidability instance for adjacency is replaced by the canonical computable decision procedure.
The theorem takes an arbitrary decidability instance for the adjacency relation of the digraph. Since `Decidable P` is a subsingleton for any proposition P (all proofs of decidability are equal), `Subsingleton.elim` proves that this instance equals the canonical computable decision procedure for the predicate u ≠ v ∧ v ≠ 4. Substituting this equality via `subst` equips the goal with the concrete computable instance.
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
It suffices to verify the bipartition conditions for the explicit vertex sets A = {0, 1} and B = {2, 3, 4}.
We provide candidate vertex subsets A = {0, 1} and B = {2, 3, 4} of Fin 5 as witnesses for the existential quantifier. This leaves four goals: that A and B are disjoint, that their union is all of Fin 5, and that the directed cut counts e(A, B) and e(B, A) are both at least 4.
refine ⟨{0, 1}, {2, 3, 4}, ?_⟩The candidate sets A = {0, 1} and B = {2, 3, 4} form a valid bipartition with directed cuts of sizes 4 and 6, each at least 4. automation
Unfolding the definition of `digraph_cut_count` expresses each cut count as the cardinality of a filtered Cartesian product of finite sets. Because the vertex set Fin 5 is finite, the disjointness, coverage, and cut inequalities (e(A, B) = 4 ≥ 4 and e(B, A) = 6 ≥ 4) are completely determined by finite arithmetic and edge enumeration, which `decide` closes by direct computation.
unfold digraph_cut_count decide
Subsingleton.elim- in a type with at most one element (a subsingleton), any two terms are equal
- Lines 7–9 are a formal Lean detail with no mathematical counterpart: because the theorem takes an abstract `DecidableRel` hypothesis, the proof replaces it with the canonical computable instance using `Subsingleton.elim` so that the `decide` tactic can perform computational reflection.
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.
/-- For the extremal digraph D₃ on 5 vertices with 16 edges and minimum outdegree 3, there exists a vertex bipartition with both directed cuts at least 4, attaining the bound of Conjecture 6.1 with equality. -/theorem digraph_apex_over_bidirected_complete_three_has_bipartition [DecidableRel (digraph_apex_over_bidirected_complete 3).Adj] : ∃ A B : Finset (Fin 5), Disjoint A B ∧ A ∪ B = Finset.univ ∧ 4 ≤ digraph_cut_count (digraph_apex_over_bidirected_complete 3) A B ∧ 4 ≤ digraph_cut_count (digraph_apex_over_bidirected_complete 3) B A := 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 refine ⟨{0, 1}, {2, 3, 4}, ?_⟩ unfold digraph_cut_count decide