AFTD Auto-Formalizing Theoretical Domains

digraph_oriented_robust_cut_twenty_one_counterexample

theoremverified

Let D be digraph_oriented_cut20_sharp_example on Fin 26 and B the set of vertices with value less than 20. D is oriented; B has at least seven vertices; every vertex of B has at least seven outneighbors in D; and every nonempty vertex set T in D for which every member has at least two outneighbors in T and at most two members have fewer than three outneighbors in T contains two vertex-disjoint directed cycles lying in T. Nevertheless B contains no two vertex-disjoint directed cycles and fewer than 21 arcs go from B to its complement.

Statement

theorem digraph_oriented_robust_cut_twenty_one_counterexample :
    let D := digraph_oriented_cut20_sharp_example
    let B : Finset (Fin 26) := Finset.univ.filter fun v => v.val < 20
    (∀ u v, D.Adj u v → ¬ D.Adj v u) ∧ 7 ≤ B.card ∧
    (∀ v ∈ B, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) ∧
    (∀ T : Finset (Fin 26), 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 26), (∀ 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 26), (∀ 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
Source
Immediate corollary of the proved oriented sharp-example certificate; the related unrestricted degree-sequence criterion is https://arxiv.org/abs/2205.10826.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The theorem is proved by reducing each claim to the precomputed certificate `digraph_oriented_cut20_sharp_example_certificate`. The certificate directly provides that the digraph D is oriented, every vertex in B has out-degree 7 (hence at least 7), the cut from B to Bᶜ has size 20 (hence fewer than 21), and D contains no two disjoint directed cycles (hence B contains none). The size bound |B| ≥ 7 is checked by direct evaluation, and the robust cycle condition on induced subgraphs T holds vacuously because any subgraph meeting the minimum degree condition has at least three vertices of out-degree less than 3, contradicting the assumption that at most two exist.

  1. The adjacency relation of the digraph `digraph_oriented_cut20_sharp_example` is decidable.

    Unfolding the definition of `digraph_oriented_cut20_sharp_example` expresses adjacency as explicit inequalities, equalities, and modular arithmetic on finite indices (`Fin 26`). Lean's typeclass resolution automatically infers decidability of this relation.

    lines 2–3

      unfold digraph_oriented_cut20_sharp_example
      infer_instance
  2. The certificate properties are introduced into the context, proving that D is oriented and that |B| ≥ 7.

    We instantiate the certificate `digraph_oriented_cut20_sharp_example_certificate` and decompose it into its five components: orientation (`ho`), exact out-degree 7 for vertices in B (`hd`), cut size 20 (`hcut`), absence of two disjoint directed cycles in D (`hno`), and the out-degree defect property for subgraphs (`hrob`). The first conjunct of the theorem is established directly by `ho`, and the second conjunct 7 ≤ |B| is verified by computational evaluation (`by decide`) since |B| = 20.

    lines 18–21

    uses digraph_oriented_cut20_sharp_example_certificate

      have h := digraph_oriented_cut20_sharp_example_certificate
      dsimp only at h ⊢
      rcases h with ⟨ho, hd, hcut, hno, hrob⟩
      refine ⟨ho, by decide, ?_, ?_, ?_, ?_⟩
  3. Every vertex in B has out-degree at least 7 in D.

    For any vertex v ∈ B, the certificate property `hd` states that the out-degree of v in D is exactly 7. Rewriting with this equality reduces the inequality 7 ≤ outdeg(v) to 7 ≤ 7, which holds reflexively.

    lines 22–23

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

    Given a nonempty subset T with minimum out-degree at least 2 and at most two vertices having out-degree less than 3, the certificate property `hrob` implies that T must actually contain at least three vertices of out-degree less than 3. The two conditions (≤ 2 and ≥ 3) are contradictory, so the implication holds vacuously, which linear integer arithmetic (`omega`) closes.

    lines 24–26

      · intro T ht hmin hbad
        have hh := hrob T ht hmin
        omega
  5. The set B contains no two vertex-disjoint directed cycles.

    Supposing for contradiction that two vertex-disjoint directed cycles exist in B, discarding the restriction to B yields two vertex-disjoint directed cycles in D. This directly contradicts the certificate property `hno`, which asserts that no such pair of cycles exists anywhere in D.

    lines 27–28

      · rintro ⟨c, hc, hdis⟩
        exact hno ⟨c, fun i => (hc i).2, hdis⟩
  6. Fewer than 21 arcs go from B to its complement.

    The certificate property `hcut` states that the number of arcs from B to its complement is exactly 20. The inequality ¬(21 ≤ 20) is then closed by linear arithmetic (`omega`).

    line 29

      · omega
digraph_oriented_cut20_sharp_example_certificate
A precomputed certificate for `digraph_oriented_cut20_sharp_example` asserting five properties: D is oriented; every vertex in B has out-degree 7; the cut from B to Bᶜ has size 20; D contains no two vertex-disjoint directed cycles; and every nonempty vertex set T with minimum out-degree at least 2 in T contains at least three vertices with out-degree strictly less than 3 in T.

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_oriented_cut20_counterexample_decAdj : DecidableRel digraph_oriented_cut20_sharp_example.Adj := by  unfold digraph_oriented_cut20_sharp_example  infer_instancetheorem digraph_oriented_robust_cut_twenty_one_counterexample :    let D := digraph_oriented_cut20_sharp_example    let B : Finset (Fin 26) := Finset.univ.filter fun v => v.val < 20    (∀ u v, D.Adj u v → ¬ D.Adj v u) ∧ 7 ≤ B.card ∧    (∀ v ∈ B, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) ∧    (∀ T : Finset (Fin 26), 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 26), (∀ 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 26), (∀ 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_oriented_cut20_sharp_example_certificate  dsimp only at h ⊢  rcases h with ⟨ho, hd, hcut, hno, hrob⟩  refine ⟨ho, by decide, ?_, ?_, ?_, ?_⟩  · intro v hv    rw [hd v hv]  · intro T ht hmin hbad    have hh := hrob T ht hmin    omega  · rintro ⟨c, hc, hdis⟩    exact hno ⟨c, fun i => (hc i).2, hdis⟩  · omega
See it in the graphDiscuss this resultChallenge it