AFTD Auto-Formalizing Theoretical Domains

digraph_local_four_witness_sources_sinks

theoremverified

For the explicit 24-vertex maximum-outdegree-four witness, every source left after deleting a closed out-neighborhood is a sink.

Statement

theorem digraph_local_four_witness_sources_sinks :
    ∀ v, ∀ u ∈ digraph_local_source_set digraph_local_four_witness v,
      digraph_local_four_witness u = ∅
Source
Auxiliary lemma for the OP-337 campaign; arXiv:2601.11847, Problem 5.2.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • 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…
Used by 1

The proof, explained

The theorem states that in the explicit 24-vertex directed graph, deleting the closed out-neighborhood of any vertex $v$ leaves an induced subgraph whose sources all have out-degree zero in the original graph (that is, they are global sinks). The proof proceeds by exhaustive verification: it fixes a vertex $v$, enumerates all 24 cases with `fin_cases`, and checks the condition for each vertex by direct finite evaluation via `decide`.

  1. Let $v$ be an arbitrary vertex in $\mathrm{Fin}\;24$.

    We fix an arbitrary vertex $v$ from the 24 vertices of the graph.

    line 7

      intro v
  2. For every vertex $u$ that is a source in the induced subgraph on the complement of the closed out-neighborhood of $v$, the out-neighborhood of $u$ is empty. automation

    We perform a complete case analysis over all 24 possible values for $v \in \mathrm{Fin}\;24$ using `fin_cases`. For each case $v \in \{0, \dots, 23\}$, the condition is a bounded, decidable statement over explicit finite sets, which is verified by direct computation using `decide`.

    line 8

      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

set_option maxRecDepth 20000set_option maxHeartbeats 4000000theorem digraph_local_four_witness_sources_sinks :    ∀ v, ∀ u ∈ digraph_local_source_set digraph_local_four_witness v,      digraph_local_four_witness u = ∅ := by  intro v  fin_cases v <;> decide
See it in the graphDiscuss this resultChallenge it