AFTD Auto-Formalizing Theoretical Domains

digraph_robust_cut_twenty_one_counterexample

theoremverifiedoriginal

Let D be digraph_cut20_sharp_example on Fin 20 and let B be the vertices with value below 13. The set B has at least seven vertices, each vertex in B has outdegree at least seven, and no two vertex-disjoint directed cycles both lie in B. For every nonempty subset T, if every vertex of T has at least two outneighbors in T and at most two vertices of T have fewer than three outneighbors in T, then T contains two vertex-disjoint directed cycles. Fewer than 21 arcs go from B to its complement.

Statement

theorem digraph_robust_cut_twenty_one_counterexample :
    let D := digraph_cut20_sharp_example
    let B : Finset (Fin 20) := Finset.univ.filter fun v => v.val < 13
    7 ≤ B.card ∧
    (∀ v ∈ B, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) ∧
    (∀ T : Finset (Fin 20), T.Nonempty →
      (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) →
      (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3).card ≤ 2 →
      ∃ c : Fin 2 → Finset (Fin 20), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j))) ∧
    (¬ ∃ c : Fin 2 → Finset (Fin 20),
      (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j))) ∧
    ¬ 21 ≤ ∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card
Related work
Adaptation of the two-cycle extremal construction in https://arxiv.org/abs/2205.10826, Figure 3.2, with sink vertices; experiments 26197 and 26198.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • digraph_cut20_sharp_exampleAn explicit 20-vertex digraph obtained by adjoining seven sink vertices to the displayed 13-vertex two-cycle obstruction.
  • digraph_directed_cycle_ons is the vertex set of a directed cycle of D: its vertices can be listed without repetition, at least two of them, each with an arc to the…
  • digraph_cut20_sharp_example_certificateIn the displayed 20-vertex graph, the first 13 vertices all have outdegree seven, exactly 20 arcs leave that set, and it contains no two…

Read back from the Lean

Let $D$ be the directed graph on vertex set $\text{Fin } 20$ defined by digraph_cut20_sharp_example, and let $B = \{v \in \text{Fin } 20 \mid v < 13\}$. The theorem asserts that all of the following five conditions hold simultaneously: 1. The cardinality of $B$ is at least 7 (i.e., $|B| \ge 7$). 2. For every vertex $v \in B$, the out-degree of $v$ in $D$ is at least 7 (i.e., $|\{w \in \text{Fin } 20 \mid D.\text{Adj}(v, w)\}| \ge 7$). 3. For every subset $T \subseteq \text{Fin } 20$, if: - $T$ is nonempty, - every vertex $v \in T$ has at least 2 out-neighbors in $T$ (i.e., $|\{w \in T \mid D.\text{Adj}(v, w)\}| \ge 2$), and - at most 2 vertices $v \in T$ have strictly fewer than 3 out-neighbors in $T$ (i.e., $|\{v \in T \mid |\{w \in T \mid D.\text{Adj}(v, w)\}| < 3\}| \le 2$), then there exist two vertex-disjoint directed cycles in $D$ that are both subsets of $T$. 4. There do not exist two vertex-disjoint directed cycles in $D$ that are both contained in $B$. 5. The number of directed edges from $B$ to its complement $B^c$ is strictly less than 21 (asserted as $\neg (21 \le \sum_{v \in B} |\{w \in B^c \mid D.\text{Adj}(v, w)\}|)$).

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 establishes that the 20-vertex directed graph D and the vertex subset B = {v ∈ Fin 20 | v < 13} satisfy five conditions, serving as a counterexample. After establishing decidability of adjacency, the proof imports `digraph_cut20_sharp_example_certificate`, which certifies degree equalities, cut size, the absence of two disjoint cycles in B, and a lower bound on low-degree vertices in induced subgraphs. From this certificate, |B| ≥ 7 holds by finite computation, outdegrees in B are at least 7 since they equal 7, the two-cycle condition holds vacuously because no such subgraph can exist, no two disjoint cycles exist in B directly by the certificate, and the cut bound holds because 20 < 21.

  1. Adjacency in the digraph `digraph_cut20_sharp_example` is decidable. automation

    We unfold the definition of the digraph, which expresses adjacency as an explicit logical combination of inequalities and modular arithmetic on `Fin 20`, and use typeclass inference (`infer_instance`) to synthesize the decidability instance.

    lines 2–3

      unfold digraph_cut20_sharp_example
      infer_instance
  2. Retrieve the certified properties of the digraph and its subset B.

    We import the pre-established lemma `digraph_cut20_sharp_example_certificate`, simplify definitions, and decompose it into four separate facts: every vertex in B has outdegree 7, the cut from B has size 20, B contains no two disjoint directed cycles, and every nonempty subgraph with minimum outdegree at least 2 has at least 3 vertices of outdegree strictly less than 3.

    lines 19–21

    uses digraph_cut20_sharp_example_certificate

      have h := digraph_cut20_sharp_example_certificate
      dsimp only at h ⊢
      rcases h with ⟨hd,hcut,hno,hrob⟩
  3. The set B has at least 7 vertices, B contains no two disjoint directed cycles, and the proof reduces to three remaining goals. automation

    We split the five-part conjunction. The first condition (|B| ≥ 7) is verified by finite computation (`decide`), since B has 13 vertices. The fourth condition (no two disjoint cycles in B) is provided directly by the certificate hypothesis `hno`. This leaves subgoals for the outdegree of vertices in B, the robust cycle condition, and the cut size.

    line 22

      refine ⟨by decide, ?_, ?_, hno, ?_⟩
  4. Each vertex in B has outdegree at least 7.

    Given an arbitrary vertex v in B, the certificate gives that its outdegree in D is exactly 7. Rewriting with this equality reduces the goal to 7 ≤ 7, which holds reflexively.

    lines 23–24

      · intro v hv
        rw [hd v hv]
  5. Any nonempty subset T with minimum outdegree at least 2 and at most two vertices of outdegree less than 3 contains two disjoint directed cycles. automation

    Suppose T is nonempty with minimum outdegree at least 2 in T and at most 2 vertices with outdegree less than 3 in T. The certificate's robustness property (`hrob`) implies that at least 3 vertices in T must have outdegree less than 3. This yields the arithmetic contradiction 3 ≤ card ≤ 2, which linear integer arithmetic (`omega`) uses to close the goal vacuously.

    lines 25–27

      · intro T ht hmin hbad
        have hh := hrob T ht hmin
        omega
  6. Fewer than 21 arcs leave B. automation

    The certificate states that the cut from B has size exactly 20. Linear arithmetic (`omega`) verifies that ¬(21 ≤ 20), closing the final goal.

    line 28

      · omega
digraph_cut20_sharp_example_certificate
For the 20-vertex digraph `digraph_cut20_sharp_example` and vertex subset B of elements with value below 13, every vertex in B has outdegree 7, the cut leaving B has size 20, B contains no two vertex-disjoint directed cycles, and every nonempty induced subgraph with minimum outdegree at least 2 contains at least 3 vertices of outdegree strictly less than 3.

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

private instance in833_cut20_counterexample_decAdj : DecidableRel digraph_cut20_sharp_example.Adj := by  unfold digraph_cut20_sharp_example  infer_instancetheorem digraph_robust_cut_twenty_one_counterexample :    let D := digraph_cut20_sharp_example    let B : Finset (Fin 20) := Finset.univ.filter fun v => v.val < 13    7 ≤ B.card ∧    (∀ v ∈ B, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) ∧    (∀ T : Finset (Fin 20), T.Nonempty →      (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) →      (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3).card ≤ 2 →      ∃ c : Fin 2 → Finset (Fin 20), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j))) ∧    (¬ ∃ c : Fin 2 → Finset (Fin 20),      (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j))) ∧    ¬ 21 ≤ ∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card := by  have h := digraph_cut20_sharp_example_certificate  dsimp only at h ⊢  rcases h with ⟨hd,hcut,hno,hrob⟩  refine ⟨by decide, ?_, ?_, hno, ?_⟩  · intro v hv    rw [hd v hv]  · intro T ht hmin hbad    have hh := hrob T ht hmin    omega  · omega
See it in the graphDiscuss this resultChallenge it