digraph_local_four_witness_combined_properties
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`.
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.
uses
digraph_local_four_witness_sources_sinksset_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, ?_⟩
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.
· intro v; fin_cases v <;> decide
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.
· intro v; fin_cases v <;> decide
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.
· intro u v; fin_cases u <;> fin_cases v <;> decide
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.
· intro v; fin_cases v <;> decide
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.
· 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).
- The verification steps in lines 14–18 rely on Lean's decision procedure `decide` to evaluate boolean expressions by computation over finite types (`Fin 24` and `Fin 24 × Fin 24`), unfolding the explicit adjacency definition and computing set operations directly.
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