AFTD Auto-Formalizing Theoretical Domains

digraph_apex_over_bidirected_complete_three_has_bipartition

theoremverifiedformalization

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.

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

    lines 7–9

    uses Subsingleton.elim

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

    line 10

      refine ⟨{0, 1}, {2, 3, 4}, ?_⟩
  3. 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.

    lines 11–12

      unfold digraph_cut_count
      decide
Subsingleton.elim
in a type with at most one element (a subsingleton), any two terms are equal

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

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