digraph_oriented_robust_cut_twenty_one_counterexample
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
- digraph_oriented_cut20_sharp_exampleThe explicit oriented 26-vertex graph with five low vertices, a target, a directed seven-cycle, seven acyclic high vertices and six sinks.
- digraph_oriented_cut20_sharp_example_certificateThe explicit oriented example has a seven-outregular twenty-vertex part with twenty outgoing arcs and no two disjoint cycles; every…
- 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…
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.
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.
unfold digraph_oriented_cut20_sharp_example infer_instance
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.
uses
digraph_oriented_cut20_sharp_example_certificatehave h := digraph_oriented_cut20_sharp_example_certificate dsimp only at h ⊢ rcases h with ⟨ho, hd, hcut, hno, hrob⟩ refine ⟨ho, by decide, ?_, ?_, ?_, ?_⟩
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.
· intro v hv rw [hd v hv]
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.
· intro T ht hmin hbad have hh := hrob T ht hmin omega
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.
· rintro ⟨c, hc, hdis⟩ exact hno ⟨c, fun i => (hc i).2, hdis⟩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`).
· 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.
- The robust cycle condition holds vacuously: the certificate ensures that no induced subgraph T satisfies the premise of having minimum out-degree at least 2 with at most two vertices of out-degree less than 3.
- Lines 1–3 define an auxiliary decidability instance for the adjacency relation of the digraph, which allows Lean to compute set cardinalities and evaluate goals via `decide`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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