digraph_robust_cut_twenty_one_counterexample
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.
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.
unfold digraph_cut20_sharp_example infer_instance
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.
uses
digraph_cut20_sharp_example_certificatehave h := digraph_cut20_sharp_example_certificate dsimp only at h ⊢ rcases h with ⟨hd,hcut,hno,hrob⟩
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.
refine ⟨by decide, ?_, ?_, hno, ?_⟩
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.
· intro v hv rw [hd v hv]
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.
· intro T ht hmin hbad have hh := hrob T ht hmin omega
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.
· 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.
- The auxiliary instance `in833_cut20_counterexample_decAdj` (lines 1–3) is a formal prerequisite establishing decidability of digraph adjacency, allowing Lean to compute with edge sets.
- The condition that any nonempty subgraph with minimum outdegree at least 2 and at most two vertices of outdegree less than 3 contains two disjoint directed cycles holds vacuously: the certificate proves that every such subgraph actually contains at least three vertices of outdegree 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
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_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