AFTD Auto-Formalizing Theoretical Domains

digraph_apex_over_bidirected_complete_two_has_bipartition

theoremverifiedformalization

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.

  1. Adjacency in D₂ is decidable.

    Unfolding the definition of D₂, the adjacency condition is a conjunction of inequalities on Fin 4, which is decidable.

    lines 1–4

    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
  2. 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.

    lines 12–14

    uses Subsingleton.elim, digraph_apex_over_bidirected_complete_two_has_bipartition_decidableRel

      have := Subsingleton.elim ‹DecidableRel (digraph_apex_over_bidirected_complete 2).Adj›
        digraph_apex_over_bidirected_complete_two_has_bipartition_decidableRel
      subst this
  3. 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.

    lines 15–16

      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

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
See it in the graphDiscuss this resultChallenge it