AFTD Auto-Formalizing Theoretical Domains

digraph_four_outdegree_five_four_counterexample

theoremverifiedoriginal

There exists a loopless source-free oriented digraph on 24 vertices with maximum outdegree at most four such that for every vertex v, if S(v) is the set of sources after deleting the closed out-neighborhood of v and E(v) is the union of the out-neighborhood of v with the out-neighborhood of S(v), then |E(v)| = |S(v)| and 5|E(v)| ≤ 4(|S(v)|+1). The graph also has an independent two-step out-dominating set of exactly six vertices.

Statement

theorem digraph_four_outdegree_five_four_counterexample :
    ∃ out : Fin 24 → Finset (Fin 24),
      (∀ v, v ∉ out v) ∧
      (∀ v, ∃ u, v ∈ out u) ∧
      (∀ u v, v ∈ out u → u ∉ out v) ∧
      (∀ v, (out v).card ≤ 4) ∧
      (∀ v, (digraph_local_source_expansion out v).card = (digraph_local_source_set out v).card ∧
        5 * (digraph_local_source_expansion out v).card ≤ 4 * ((digraph_local_source_set out v).card + 1)) ∧
      (∃ Q : Finset (Fin 24), Q.card = 6 ∧
        (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → v ∉ out u) ∧
        (∀ v, ∃ u ∈ Q, u = v ∨ v ∈ out u ∨ ∃ w, w ∈ out u ∧ v ∈ out w))
Related work
arXiv:2601.11847, Problem 5.2 and Proposition 2.3; a local-obstruction construction used in the OP-337 campaign.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • digraph_local_source_setGiven finite out-neighborhood sets and a vertex v, the vertices outside the closed out-neighborhood of v that have no in-neighbor outside…
  • digraph_local_source_expansionThe union of the out-neighborhood of v and the out-neighborhoods of the sources remaining after deletion of the closed out-neighborhood of…
  • digraph_local_four_witnessA 24-vertex oriented digraph specified by its out-neighborhoods: an eight-vertex two-outregular core with two private sink leaves at each…

Read back from the Lean

There exists a directed graph on 24 vertices (represented by an out-neighborhood function out : Fin 24 → Finset (Fin 24)) such that: 1. The graph has no self-loops: for every vertex $v$, $v \notin out(v)$. 2. Every vertex has in-degree at least 1: for every vertex $v$, there exists a vertex $u$ such that $v \in out(u)$. 3. The graph has no 2-cycles (is an oriented graph): for all vertices $u, v$, if $v \in out(u)$, then $u \notin out(v)$. 4. Every vertex has out-degree at most 4: for every vertex $v$, $|out(v)| \le 4$. 5. For every vertex $v$, the cardinality of digraph_local_source_expansion out v equals the cardinality of digraph_local_source_set out v, and $5 \cdot |\text{digraph\_local\_source\_expansion out v}| \le 4 \cdot (|\text{digraph\_local\_source\_set out v}| + 1)$. 6. There exists a subset $Q \subseteq \text{Fin } 24$ of size 6 such that: - $Q$ is an independent set: for all distinct $u, v \in Q$, $v \notin out(u)$; - $Q$ is a distance-2 dominating set: for every vertex $v$, there exists $u \in Q$ such that $u = v$, or $v \in out(u)$, or there exists some $w$ such that $w \in out(u)$ and $v \in out(w)$ (i.e., $v$ is reachable from $u$ by a directed path of length at most 2).

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 is established constructively by exhibiting an explicit 24-vertex oriented digraph, digraph_local_four_witness, where eight vertices (0 through 7) have outdegree four and the remaining sixteen (8 through 23) have outdegree zero. All required conditions—looplessness, source-freedom, orientation, maximum outdegree at most four, the local source expansion condition, and the existence of an independent six-vertex two-step dominating set Q = {0, 1, 12, 13, 20, 21}—are finite properties over the 24 vertices. The proof verifies each property exhaustively across all vertices and pairs via finite case analysis (fin_cases) and boolean reflection (decide).

  1. It suffices to verify the six graph properties for the concrete 24-vertex digraph digraph_local_four_witness.

    We instantiate the existential quantifier with the explicit witness digraph_local_four_witness, reducing the goal to six subgoals corresponding to the conjunctions: looplessness, positive in-degrees (source-free), orientation (no 2-cycles), maximum outdegree at most 4, the local source expansion condition, and the existence of an independent 2-step out-dominating set of size 6.

    line 15

      refine ⟨digraph_local_four_witness, ?_, ?_, ?_, ?_, ?_, ?_⟩
  2. The digraph is loopless (no vertex has a directed edge to itself). automation

    For an arbitrary vertex v, exhaustive case analysis on all 24 vertices of Fin 24 (via fin_cases v) reduces the claim to 24 membership checks, each closed by computational evaluation (decide).

    line 16

      · intro v; fin_cases v <;> decide
  3. Every vertex has at least one incoming edge (the digraph is source-free). automation

    Splitting into cases across all 24 vertices (fin_cases v), an explicit in-neighbor u with v ∈ out(u) is found and verified for each vertex by finite computation (decide).

    line 17

      · intro v; fin_cases v <;> decide
  4. The digraph is oriented (there are no directed 2-cycles). automation

    Exhaustive case analysis on all 24 × 24 = 576 pairs of vertices (u, v) via fin_cases u <;> fin_cases v reduces the condition v ∈ out(u) → u ∉ out(v) to finite boolean checks closed by decide.

    line 18

      · intro u v; fin_cases u <;> fin_cases v <;> decide
  5. The maximum outdegree of every vertex is at most 4. automation

    Case analysis on the 24 vertices (fin_cases v) checks that the cardinality of the out-neighborhood is at most 4 (vertices 0 through 7 have outdegree 4, while vertices 8 through 23 have outdegree 0), verified by decide.

    line 19

      · intro v; fin_cases v <;> decide
  6. For every vertex v, the local source set S(v) and its expansion E(v) satisfy |E(v)| = |S(v)| and 5|E(v)| ≤ 4(|S(v)| + 1). automation

    Splitting across all 24 vertices (fin_cases v) and separating the conjunction into two goals (constructor), the local source set S(v) and its out-neighborhood expansion E(v) are evaluated according to their definitions, and their cardinalities are computed and verified by decide.

    line 20

      · intro v; fin_cases v <;> constructor <;> decide
  7. There exists an independent set Q of size 6 that two-step out-dominates the digraph. automation

    We provide the explicit candidate set Q = {0, 1, 12, 13, 20, 21}. Its cardinality |Q| = 6 is verified by direct calculation (by decide). Independence (no directed edge between distinct elements of Q) is verified by evaluating all pairs in Q (decide). Finally, two-step out-domination (every vertex in the graph is in Q, an out-neighbor of Q, or an out-neighbor of an out-neighbor of Q) is verified by testing all 24 vertices (fin_cases v <;> decide).

    lines 21–23

      · refine ⟨{0,1,12,13,20,21}, by decide, ?_, ?_⟩
        · decide
        · intro v; fin_cases v <;> 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

Lean’s trace was cut to the first 400 of 784 tactics.

set_option maxRecDepth 20000set_option maxHeartbeats 4000000theorem digraph_four_outdegree_five_four_counterexample :    ∃ out : Fin 24 → Finset (Fin 24),      (∀ v, v ∉ out v) ∧      (∀ v, ∃ u, v ∈ out u) ∧      (∀ u v, v ∈ out u → u ∉ out v) ∧      (∀ v, (out v).card ≤ 4) ∧      (∀ v, (digraph_local_source_expansion out v).card = (digraph_local_source_set out v).card ∧        5 * (digraph_local_source_expansion out v).card ≤ 4 * ((digraph_local_source_set out v).card + 1)) ∧      (∃ Q : Finset (Fin 24), Q.card = 6 ∧        (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → v ∉ out u) ∧        (∀ v, ∃ u ∈ Q, u = v ∨ v ∈ out u ∨ ∃ w, w ∈ out u ∧ v ∈ out w)) := by  refine ⟨digraph_local_four_witness, ?_, ?_, ?_, ?_, ?_, ?_⟩  · intro v; fin_cases v <;> decide  · intro v; fin_cases v <;> decide  · intro u v; fin_cases u <;> fin_cases v <;> decide  · intro v; fin_cases v <;> decide  · intro v; fin_cases v <;> constructor <;> decide  · refine ⟨{0,1,12,13,20,21}, by decide, ?_, ?_⟩    · decide    · intro v; fin_cases v <;> decide
See it in the graphDiscuss this resultChallenge it