AFTD Auto-Formalizing Theoretical Domains

digraph_apex_over_bidirected_complete_three_max_min_cut

theoremverified

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

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

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

    lines 6–8

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

    line 9

      unfold digraph_cut_count digraph_edge_count
  3. For 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.

    line 10

      decide
Subsingleton.elim
Any two elements of a type that has at most one element (a subsingleton) 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

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