digraph_apex_over_bidirected_complete_two_has_bipartition
There exists a vertex bipartition V = A ⊔ B of the apex digraph D₂ on 4 vertices such that both directed cut counts e(A, B) and e(B, A) are at least 2, satisfying the bound ⌈(2 - 1) * 9 / (2 * (2 * 2 - 1))⌉ = 2 of Conjecture 6.1 of arXiv:2610.21381.
Statement
theorem digraph_apex_over_bidirected_complete_two_has_bipartition
[DecidableRel (digraph_apex_over_bidirected_complete 2).Adj] :
∃ A B : Finset (Fin 4), Disjoint A B ∧ A ∪ B = Finset.univ ∧
2 ≤ digraph_cut_count (digraph_apex_over_bidirected_complete 2) A B ∧
2 ≤ digraph_cut_count (digraph_apex_over_bidirected_complete 2) 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 2 is decidable, there exist two finsets $A, B \subseteq \mathrm{Fin}\ 4$ such that:
1. $A$ and $B$ are disjoint,
2. $A \cup B = \mathrm{Finset.univ}$ (i.e., $A$ and $B$ form a bipartition of $\mathrm{Fin}\ 4$),
3. The cut count from $A$ to $B$ in digraph_apex_over_bidirected_complete 2 is at least 2, and
4. The cut count from $B$ to $A$ in digraph_apex_over_bidirected_complete 2 is at least 2.
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 proof exhibits an explicit vertex partition A = {0} and B = {1, 2, 3} of the 4-vertex apex digraph D₂. After replacing the theorem's abstract decidability hypothesis with a computable instance via subsingleton elimination, the disjointness, coverage, and directed cut bounds (e(A, B) = 2 and e(B, A) = 3) are verified by direct finite computation.
Adjacency in D₂ is decidable.
Unfolding the definition of D₂, the adjacency condition is a conjunction of inequalities on Fin 4, which is decidable.
instance digraph_apex_over_bidirected_complete_two_has_bipartition_decidableRel : DecidableRel (digraph_apex_over_bidirected_complete 2).Adj := by dsimp [digraph_apex_over_bidirected_complete] infer_instance
The assumed decidability instance can be replaced by the concrete computable instance.
Since Decidable is a subsingleton, any two decidability instances are equal. We replace the arbitrary instance in the theorem's hypotheses with the computable instance.
uses
Subsingleton.elim,digraph_apex_over_bidirected_complete_two_has_bipartition_decidableRelhave := Subsingleton.elim ‹DecidableRel (digraph_apex_over_bidirected_complete 2).Adj› digraph_apex_over_bidirected_complete_two_has_bipartition_decidableRel subst this
The partition A = {0} and B = {1, 2, 3} satisfies the disjointness, coverage, and cut count requirements.
We choose A = {0} and B = {1, 2, 3}, and verify all four conditions by computation.
refine ⟨{0}, {1, 2, 3}, ?_⟩ decide
Subsingleton.elim- Any two elements of a subsingleton type are equal.
digraph_apex_over_bidirected_complete_two_has_bipartition_decidableRel- The adjacency relation on D₂ is decidable.
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.
instance digraph_apex_over_bidirected_complete_two_has_bipartition_decidableRel : DecidableRel (digraph_apex_over_bidirected_complete 2).Adj := by dsimp [digraph_apex_over_bidirected_complete] infer_instance/-- For the digraph D₂ on 4 vertices with 9 edges and minimum outdegree 2, there exists a vertex bipartition with both directed cuts at least 2, matching the bound of Conjecture 6.1. -/theorem digraph_apex_over_bidirected_complete_two_has_bipartition [DecidableRel (digraph_apex_over_bidirected_complete 2).Adj] : ∃ A B : Finset (Fin 4), Disjoint A B ∧ A ∪ B = Finset.univ ∧ 2 ≤ digraph_cut_count (digraph_apex_over_bidirected_complete 2) A B ∧ 2 ≤ digraph_cut_count (digraph_apex_over_bidirected_complete 2) B A := by have := Subsingleton.elim ‹DecidableRel (digraph_apex_over_bidirected_complete 2).Adj› digraph_apex_over_bidirected_complete_two_has_bipartition_decidableRel subst this refine ⟨{0}, {1, 2, 3}, ?_⟩ decide