digraph_overlap_sharp_eight_certificate
The displayed eight-vertex graph is loopless, oriented and arc-dominated; vertex 7 is a sink. Its only unordered pair of vertices with at least two common predecessors is 2 and 7, which has exactly three common predecessors, namely 0, 1 and 5.
Statement
theorem digraph_overlap_sharp_eight_certificate : (∀ u, ¬ digraph_overlap_sharp_eight_graph.Adj u u) ∧ (∀ u v, digraph_overlap_sharp_eight_graph.Adj u v → ¬ digraph_overlap_sharp_eight_graph.Adj v u) ∧ (∀ u v, digraph_overlap_sharp_eight_graph.Adj u v → ∃ p, digraph_overlap_sharp_eight_graph.Adj p u ∧ digraph_overlap_sharp_eight_graph.Adj p v) ∧ (∀ v, ¬ digraph_overlap_sharp_eight_graph.Adj 7 v) ∧ (∀ a b : Fin 8, a.val < b.val → (2 ≤ (Finset.univ.filter fun p => digraph_overlap_sharp_eight_graph.Adj p a ∧ digraph_overlap_sharp_eight_graph.Adj p b).card ↔ a = 2 ∧ b = 7)) ∧ ((Finset.univ.filter fun p => digraph_overlap_sharp_eight_graph.Adj p 2 ∧ digraph_overlap_sharp_eight_graph.Adj p 7).card = 3) ∧ (∀ p ∈ ({0, 1, 5} : Finset (Fin 8)), digraph_overlap_sharp_eight_graph.Adj p 2 ∧ digraph_overlap_sharp_eight_graph.Adj p 7)
- Source
- Finite witness that the dirty-parent plus missing-image-arc accounting can attain three times overlap in the OP-110 route; experiment 13163.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_overlap_sharp_eight_graphThe oriented graph on eight vertices obtained from the cyclic graph on seven vertices with steps 1, 2 and 4 by adding a sink with…
The proof, explained
The theorem verifies that a concrete eight-vertex directed graph—consisting of a Paley tournament on vertices 0 through 6 together with a sink vertex 7 receiving arcs from 0, 1, and 5—satisfies seven structural conditions. First, decidability of the adjacency relation is established by unfolding its definition into decidable arithmetic and finite set operations. Because the vertex set Fin 8 is finite, each of the seven conjuncts (looplessness, orientation, arc domination, sink status of 7, uniqueness of {2, 7} having at least two common predecessors, and the exact count and identities of those predecessors) is verified by exhaustive finite computation using the `decide` tactic.
The adjacency relation of the graph is decidable for all pairs of vertices.
Given two vertices u and v in Fin 8, unfolding the definition of digraph_overlap_sharp_eight_graph expresses adjacency in terms of arithmetic inequalities, modulo operations, and membership in finite sets. Because these operations on finite types are decidable, typeclass synthesis (`infer_instance`) constructs the decision procedure.
intro u v unfold digraph_overlap_sharp_eight_graph infer_instance
The graph is loopless (has no self-loops). automation
The first conjunct, requiring that no vertex u has an edge to itself, is split off using `constructor` and closed by exhaustive evaluation across all 8 vertices using `decide`.
constructor · decide
The graph is oriented (contains no directed 2-cycles). automation
The second conjunct, requiring that an edge from u to v precludes an edge from v to u, is split off using `constructor` and verified for all 64 pairs of vertices by `decide`.
constructor · decide
The graph is arc-dominated. automation
The third conjunct asserts that for every directed edge u → v, there exists some vertex p that is a common predecessor of both u and v. This existential condition is split off with `constructor` and verified for all edges by exhaustive search using `decide`.
constructor · decide
Vertex 7 is a sink. automation
The fourth conjunct, asserting that vertex 7 has no outgoing edges to any vertex v, is split off with `constructor` and verified for all 8 possible targets by `decide`.
constructor · decide
The pair {2, 7} is the unique unordered pair of vertices sharing at least two common predecessors. automation
The fifth conjunct asserts that for any pair of vertices a < b, the number of common predecessors of a and b is at least 2 if and only if a = 2 and b = 7. This equivalence is split off with `constructor` and verified across all 28 pairs of distinct vertices using `decide`.
constructor · decide
Vertices 2 and 7 have exactly three common predecessors, namely 0, 1, and 5. automation
The remaining conjunction is split with `constructor`. The first subclause states that the cardinality of the common predecessor set of 2 and 7 is 3, which `decide` verifies by direct evaluation. The second subclause states that each of 0, 1, and 5 is a common predecessor of 2 and 7, which `decide` likewise confirms by evaluating the adjacency conditions.
constructor · decide · decide
- The proof relies entirely on computational reflection via Lean's `decide` tactic: rather than symbolic mathematical deductions, Lean checks each property by exhaustively evaluating decidable predicates over the finite domain of 8 vertices (and the 28 pairs of vertices).
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 in504_sharp_decAdj : DecidableRel digraph_overlap_sharp_eight_graph.Adj := by intro u v unfold digraph_overlap_sharp_eight_graph infer_instanceset_option maxHeartbeats 0set_option maxRecDepth 100000theorem digraph_overlap_sharp_eight_certificate : (∀ u, ¬ digraph_overlap_sharp_eight_graph.Adj u u) ∧ (∀ u v, digraph_overlap_sharp_eight_graph.Adj u v → ¬ digraph_overlap_sharp_eight_graph.Adj v u) ∧ (∀ u v, digraph_overlap_sharp_eight_graph.Adj u v → ∃ p, digraph_overlap_sharp_eight_graph.Adj p u ∧ digraph_overlap_sharp_eight_graph.Adj p v) ∧ (∀ v, ¬ digraph_overlap_sharp_eight_graph.Adj 7 v) ∧ (∀ a b : Fin 8, a.val < b.val → (2 ≤ (Finset.univ.filter fun p => digraph_overlap_sharp_eight_graph.Adj p a ∧ digraph_overlap_sharp_eight_graph.Adj p b).card ↔ a = 2 ∧ b = 7)) ∧ ((Finset.univ.filter fun p => digraph_overlap_sharp_eight_graph.Adj p 2 ∧ digraph_overlap_sharp_eight_graph.Adj p 7).card = 3) ∧ (∀ p ∈ ({0, 1, 5} : Finset (Fin 8)), digraph_overlap_sharp_eight_graph.Adj p 2 ∧ digraph_overlap_sharp_eight_graph.Adj p 7) := by constructor · decide constructor · decide constructor · decide constructor · decide constructor · decide constructor · decide · decide