AFTD Auto-Formalizing Theoretical Domains

digraph_local_four_witness_combined_properties

theoremverified

The explicit 24-vertex witness is source-free and oriented with maximum outdegree four; all sources after any closed out-neighborhood deletion are sinks, and the local expansion satisfies the 5/4 inequality at every vertex.

Statement

theorem digraph_local_four_witness_combined_properties :
    (∀ v, v ∉ digraph_local_four_witness v) ∧
    (∀ v, ∃ u, v ∈ digraph_local_four_witness u) ∧
    (∀ u v, v ∈ digraph_local_four_witness u → u ∉ digraph_local_four_witness v) ∧
    (∀ v, (digraph_local_four_witness v).card ≤ 4) ∧
    (∀ v, ∀ u ∈ digraph_local_source_set digraph_local_four_witness v,
      digraph_local_four_witness u = ∅) ∧
    (∀ v, 5 * (digraph_local_source_expansion digraph_local_four_witness v).card ≤
      4 * ((digraph_local_source_set digraph_local_four_witness v).card + 1))
Source
arXiv:2601.11847, Theorem 1.2 and Problem 5.2; accompanying certificate for the OP-337 local obstruction.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • 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_witness_sources_sinksFor the explicit 24-vertex maximum-outdegree-four witness, every source left after deleting a closed out-neighborhood is a sink.

The proof, explained

The theorem establishes six structural properties of an explicit 24-vertex directed graph: it has no self-loops, no sources, no 2-cycles, maximum out-degree at most 4, every source created by deleting a closed out-neighborhood is an original sink, and every vertex satisfies a 5/4 local expansion bound. The proof splits the conjunction into these six parts: the property regarding sources becoming sinks is resolved by the previously proved lemma `digraph_local_four_witness_sources_sinks`, while the other five properties are each proved by exhaustive case analysis over the 24 vertices (or all 576 pairs) using the finite decision procedure `decide`.

  1. Evaluation resource limits are increased, and the six-part conjunction reduces to five finite verification goals, with the fifth conjunct supplied by a previously established lemma.

    The recursion depth and heartbeat limits are raised (`maxRecDepth 20000`, `maxHeartbeats 4000000`) so that exhaustive finite case-checking can complete without exhaustion. The theorem asserts a conjunction of six properties. The proof refines the goal into six parts, providing `digraph_local_four_witness_sources_sinks` for the fifth component (which asserts that sources after out-neighborhood deletion are sinks), leaving the remaining five conditions to be proven independently.

    lines 1–13

    uses digraph_local_four_witness_sources_sinks

    set_option maxRecDepth 20000
    set_option maxHeartbeats 4000000
    
    theorem digraph_local_four_witness_combined_properties :
        (∀ v, v ∉ digraph_local_four_witness v) ∧
        (∀ v, ∃ u, v ∈ digraph_local_four_witness u) ∧
        (∀ u v, v ∈ digraph_local_four_witness u → u ∉ digraph_local_four_witness v) ∧
        (∀ v, (digraph_local_four_witness v).card ≤ 4) ∧
        (∀ v, ∀ u ∈ digraph_local_source_set digraph_local_four_witness v,
          digraph_local_four_witness u = ∅) ∧
        (∀ v, 5 * (digraph_local_source_expansion digraph_local_four_witness v).card ≤
          4 * ((digraph_local_source_set digraph_local_four_witness v).card + 1)) := by
      refine ⟨?_, ?_, ?_, ?_, digraph_local_four_witness_sources_sinks, ?_⟩
  2. The graph has no self-loops: every vertex v satisfies v ∉ N⁺(v). automation

    For an arbitrary vertex v, an exhaustive case analysis across all 24 vertices (`fin_cases v`) is performed. For each vertex, the decision procedure `decide` evaluates the definition of the out-neighborhood and verifies that v is not an element of it.

    line 14

      · intro v; fin_cases v <;> decide
  3. The graph has no sources: every vertex v has at least one incoming edge (is in the out-neighborhood of some vertex u). automation

    For each vertex v among the 24 vertices (`fin_cases v`), `decide` searches the finite set of vertices to find an in-neighbor u and confirms the existential claim by computation.

    line 15

      · intro v; fin_cases v <;> decide
  4. The graph is oriented (asymmetric): there are no 2-cycles, so v ∈ N⁺(u) implies u ∉ N⁺(v) for all pairs u, v. automation

    Case exhaustion over all 24 × 24 = 576 pairs of vertices (u, v) is performed using `fin_cases u` and `fin_cases v`. For each pair, `decide` computes the truth value of the implication from the explicit edge definitions.

    line 16

      · intro u v; fin_cases u <;> fin_cases v <;> decide
  5. Every vertex has out-degree at most 4: |N⁺(v)| ≤ 4 for all v. automation

    Exhaustive case analysis over all 24 vertices (`fin_cases v`) reduces the claim to 24 concrete inequalities. For each vertex v, `decide` calculates the cardinality of N⁺(v) and verifies it does not exceed 4.

    line 17

      · intro v; fin_cases v <;> decide
  6. The 5/4 local expansion inequality holds at every vertex: 5 · |Nₑₓₚ(v)| ≤ 4 · (|S(v)| + 1) for all v. automation

    By case analysis on all 24 vertices (`fin_cases v`), the condition is checked for each vertex individually. The decision procedure `decide` computes the source set S(v) and the expanded neighborhood Nₑₓₚ(v) by evaluating finite set filters and unions, counts their elements, and verifies the arithmetic inequality.

    line 18

      · intro v; fin_cases v <;> decide
digraph_local_four_witness_sources_sinks
In the 24-vertex witness graph, for every vertex v, every vertex u that becomes a source in the subgraph after deleting the closed out-neighborhood of v is a sink in the original graph (its out-degree is 0).

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). 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_combined_properties :    (∀ v, v ∉ digraph_local_four_witness v) ∧    (∀ v, ∃ u, v ∈ digraph_local_four_witness u) ∧    (∀ u v, v ∈ digraph_local_four_witness u → u ∉ digraph_local_four_witness v) ∧    (∀ v, (digraph_local_four_witness v).card ≤ 4) ∧    (∀ v, ∀ u ∈ digraph_local_source_set digraph_local_four_witness v,      digraph_local_four_witness u = ∅) ∧    (∀ v, 5 * (digraph_local_source_expansion digraph_local_four_witness v).card ≤      4 * ((digraph_local_source_set digraph_local_four_witness v).card + 1)) := by  refine ⟨?_, ?_, ?_, ?_, digraph_local_four_witness_sources_sinks, ?_⟩  · 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 <;> decide
See it in the graphDiscuss this resultChallenge it