digraph_two_overlap_good_center_counterexample
The displayed thirteen-vertex graph is loopless, oriented and arc-dominated, has common-predecessor overlap six, and has no vertex whose out-neighborhood is clean and whose every outgoing arc has a common successor. Thus the general good-center conclusion can fail even when twice the overlap is smaller than the number of vertices.
Statement
theorem digraph_two_overlap_good_center_counterexample : (∀ u, ¬ digraph_two_overlap_counterexample_graph.Adj u u) ∧ (∀ u v, digraph_two_overlap_counterexample_graph.Adj u v → ¬ digraph_two_overlap_counterexample_graph.Adj v u) ∧ (∀ u v, digraph_two_overlap_counterexample_graph.Adj u v → ∃ p, digraph_two_overlap_counterexample_graph.Adj p u ∧ digraph_two_overlap_counterexample_graph.Adj p v) ∧ ((∑ u : Fin 13, Nat.choose (Finset.univ.filter fun v => digraph_two_overlap_counterexample_graph.Adj u v).card 2) - (digraph_common_predecessor_graph digraph_two_overlap_counterexample_graph).edgeFinset.card = 6) ∧ ¬ ∃ u : Fin 13, (∀ a b, a ≠ b → digraph_two_overlap_counterexample_graph.Adj u a → digraph_two_overlap_counterexample_graph.Adj u b → ∀ p, digraph_two_overlap_counterexample_graph.Adj p a → digraph_two_overlap_counterexample_graph.Adj p b → p = u) ∧ (∀ v, digraph_two_overlap_counterexample_graph.Adj u v → ∃ w, digraph_two_overlap_counterexample_graph.Adj u w ∧ digraph_two_overlap_counterexample_graph.Adj v w)
- Source
- Finite counterexample discovered in experiment 13185 and independently checked in 13186; serves the OP-110 small-overlap route.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- digraph_two_overlap_counterexample_graphThe explicit 13-vertex oriented digraph listed by the recorded finite counterexample.
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- Used by 1
- digraph_two_overlap_good_center_criterion_falseIt is false that every oriented arc-dominated loopless digraph on thirteen vertices with twice its common-predecessor overlap below…
The proof, explained
The theorem proves that a specific 13-vertex directed graph is loopless, oriented, arc-dominated, has common-predecessor overlap 6, and contains no vertex with both a clean out-neighborhood and the good center property. The first four structural conditions are verified by finite exhaustive evaluation via the `decide` tactic. The final non-existence claim is proved by contradiction using case analysis on all 13 vertices: vertices 0 through 6 cannot have clean out-neighborhoods because pairs of their out-neighbors share another common predecessor, while vertices 7 through 12 cannot be good centers because each has an outgoing arc with no common successor.
Adjacency in the 13-vertex graph is decidable. automation
For any pair of vertices u and v in Fin 13, the graph definition is unfolded into membership testing in an explicit 45-element list of directed edges, which Lean's typeclass inference synthesizes as a decidable relation.
intro u v unfold digraph_two_overlap_counterexample_graph infer_instance
Adjacency in the common-predecessor graph is decidable. automation
For any vertices u and v, adjacency in the common-predecessor graph unfolds into the inequality u ≠ v and an existential quantifier over the finite domain Fin 13, which typeclass inference automatically decides.
intro u v unfold digraph_common_predecessor_graph infer_instance
The graph has no self-loops. automation
Splitting the first conjunct of the theorem with `constructor`, Lean verifies by exhaustive finite evaluation (`decide`) that no vertex has an edge to itself.
constructor · decide
The graph is oriented (asymmetric). automation
Splitting the next conjunct, Lean evaluates all pairs by `decide` to confirm that if u → v then v does not point to u, meaning there are no 2-cycles.
constructor · decide
The graph is arc-dominated. automation
Splitting the next conjunct, Lean checks by exhaustive search (`decide`) that for every directed edge u → v, there exists a common predecessor p pointing to both u and v.
constructor · decide
The common-predecessor overlap of the graph is exactly 6. automation
Splitting the next conjunct, Lean evaluates the sum of binomial coefficients Nat.choose (out-degree of u) 2 minus the number of edges of the common-predecessor graph, confirming by finite computation (`decide`) that this excess multiplicity equals 6.
constructor · decide
Assume for contradiction that a vertex u has a clean out-neighborhood and the good center property, and split into cases for each vertex.
We assume for contradiction the existence of a vertex u satisfying both `hclean` (no two out-neighbors of u share any other common predecessor) and `hgood` (every out-neighbor of u shares a common successor with u), and use `fin_cases u` to analyze all 13 possible values in Fin 13.
· rintro ⟨u, hclean, hgood⟩ fin_cases uVertices 0 through 6 fail the clean out-neighborhood condition.
For each u ∈ {0, ..., 6}, we apply `hclean` to two distinct out-neighbors that share another predecessor p ≠ u: for u = 0, neighbors 1 and 12 share predecessor 4; for u = 1, neighbors 2 and 7 share predecessor 0; for u = 2, neighbors 3 and 11 share predecessor 6; for u = 3, neighbors 4 and 8 share predecessor 0; for u = 4, neighbors 1 and 12 share predecessor 0; for u = 5, neighbors 2 and 7 share predecessor 0; and for u = 6, neighbors 1 and 12 share predecessor 0. In each case, `hclean` deduces p = u, which contradicts the known inequality p ≠ u.
· have heq := hclean 1 12 (by decide) (by decide) (by decide) 4 (by decide) (by decide) exact (by decide : (4 : Fin 13) ≠ 0) heq · have heq := hclean 2 7 (by decide) (by decide) (by decide) 0 (by decide) (by decide) exact (by decide : (0 : Fin 13) ≠ 1) heq · have heq := hclean 3 11 (by decide) (by decide) (by decide) 6 (by decide) (by decide) exact (by decide : (6 : Fin 13) ≠ 2) heq · have heq := hclean 4 8 (by decide) (by decide) (by decide) 0 (by decide) (by decide) exact (by decide : (0 : Fin 13) ≠ 3) heq · have heq := hclean 1 12 (by decide) (by decide) (by decide) 0 (by decide) (by decide) exact (by decide : (0 : Fin 13) ≠ 4) heq · have heq := hclean 2 7 (by decide) (by decide) (by decide) 0 (by decide) (by decide) exact (by decide : (0 : Fin 13) ≠ 5) heq · have heq := hclean 1 12 (by decide) (by decide) (by decide) 0 (by decide) (by decide) exact (by decide : (0 : Fin 13) ≠ 6) heq
Vertices 7 through 12 fail the good center condition.
For each u ∈ {7, ..., 12}, applying `hgood` to an out-neighbor v produces an alleged common successor w, but finite exhaustive evaluation (`decide`) proves that no such common successor exists: the pairs of out-neighborhoods for (7, 9), (8, 10), (9, 10), (10, 1), (11, 0), and (12, 11) are each disjoint.
· have h := hgood 9 (by decide) have hn : ¬ ∃ w : Fin 13, digraph_two_overlap_counterexample_graph.Adj 7 w ∧ digraph_two_overlap_counterexample_graph.Adj 9 w := by decide exact hn h · have h := hgood 10 (by decide) have hn : ¬ ∃ w : Fin 13, digraph_two_overlap_counterexample_graph.Adj 8 w ∧ digraph_two_overlap_counterexample_graph.Adj 10 w := by decide exact hn h · have h := hgood 10 (by decide) have hn : ¬ ∃ w : Fin 13, digraph_two_overlap_counterexample_graph.Adj 9 w ∧ digraph_two_overlap_counterexample_graph.Adj 10 w := by decide exact hn h · have h := hgood 1 (by decide) have hn : ¬ ∃ w : Fin 13, digraph_two_overlap_counterexample_graph.Adj 10 w ∧ digraph_two_overlap_counterexample_graph.Adj 1 w := by decide exact hn h · have h := hgood 0 (by decide) have hn : ¬ ∃ w : Fin 13, digraph_two_overlap_counterexample_graph.Adj 11 w ∧ digraph_two_overlap_counterexample_graph.Adj 0 w := by decide exact hn h · have h := hgood 11 (by decide) have hn : ¬ ∃ w : Fin 13, digraph_two_overlap_counterexample_graph.Adj 12 w ∧ digraph_two_overlap_counterexample_graph.Adj 11 w := by decide exact hn h
- The graph properties (looplessness, asymmetry, arc-domination, the overlap count, and the absence of common successors) are established by exhaustive finite verification using Lean's `decide` tactic, enabled by decidability instances synthesized for adjacency.
- The compiler options `maxHeartbeats 0` and `maxRecDepth 100000` disable heartbeat limits and increase recursion depth to accommodate the heavy compile-time computation required by `decide` on Fin 13.
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_no_good_decAdj : DecidableRel digraph_two_overlap_counterexample_graph.Adj := by intro u v unfold digraph_two_overlap_counterexample_graph infer_instanceprivate instance in504_no_good_aux_decAdj : DecidableRel (digraph_common_predecessor_graph digraph_two_overlap_counterexample_graph).Adj := by intro u v unfold digraph_common_predecessor_graph infer_instanceset_option maxHeartbeats 0set_option maxRecDepth 100000theorem digraph_two_overlap_good_center_counterexample : (∀ u, ¬ digraph_two_overlap_counterexample_graph.Adj u u) ∧ (∀ u v, digraph_two_overlap_counterexample_graph.Adj u v → ¬ digraph_two_overlap_counterexample_graph.Adj v u) ∧ (∀ u v, digraph_two_overlap_counterexample_graph.Adj u v → ∃ p, digraph_two_overlap_counterexample_graph.Adj p u ∧ digraph_two_overlap_counterexample_graph.Adj p v) ∧ ((∑ u : Fin 13, Nat.choose (Finset.univ.filter fun v => digraph_two_overlap_counterexample_graph.Adj u v).card 2) - (digraph_common_predecessor_graph digraph_two_overlap_counterexample_graph).edgeFinset.card = 6) ∧ ¬ ∃ u : Fin 13, (∀ a b, a ≠ b → digraph_two_overlap_counterexample_graph.Adj u a → digraph_two_overlap_counterexample_graph.Adj u b → ∀ p, digraph_two_overlap_counterexample_graph.Adj p a → digraph_two_overlap_counterexample_graph.Adj p b → p = u) ∧ (∀ v, digraph_two_overlap_counterexample_graph.Adj u v → ∃ w, digraph_two_overlap_counterexample_graph.Adj u w ∧ digraph_two_overlap_counterexample_graph.Adj v w) := by constructor · decide constructor · decide constructor · decide constructor · decide · rintro ⟨u, hclean, hgood⟩ fin_cases u · have heq := hclean 1 12 (by decide) (by decide) (by decide) 4 (by decide) (by decide) exact (by decide : (4 : Fin 13) ≠ 0) heq · have heq := hclean 2 7 (by decide) (by decide) (by decide) 0 (by decide) (by decide) exact (by decide : (0 : Fin 13) ≠ 1) heq · have heq := hclean 3 11 (by decide) (by decide) (by decide) 6 (by decide) (by decide) exact (by decide : (6 : Fin 13) ≠ 2) heq · have heq := hclean 4 8 (by decide) (by decide) (by decide) 0 (by decide) (by decide) exact (by decide : (0 : Fin 13) ≠ 3) heq · have heq := hclean 1 12 (by decide) (by decide) (by decide) 0 (by decide) (by decide) exact (by decide : (0 : Fin 13) ≠ 4) heq · have heq := hclean 2 7 (by decide) (by decide) (by decide) 0 (by decide) (by decide) exact (by decide : (0 : Fin 13) ≠ 5) heq · have heq := hclean 1 12 (by decide) (by decide) (by decide) 0 (by decide) (by decide) exact (by decide : (0 : Fin 13) ≠ 6) heq · have h := hgood 9 (by decide) have hn : ¬ ∃ w : Fin 13, digraph_two_overlap_counterexample_graph.Adj 7 w ∧ digraph_two_overlap_counterexample_graph.Adj 9 w := by decide exact hn h · have h := hgood 10 (by decide) have hn : ¬ ∃ w : Fin 13, digraph_two_overlap_counterexample_graph.Adj 8 w ∧ digraph_two_overlap_counterexample_graph.Adj 10 w := by decide exact hn h · have h := hgood 10 (by decide) have hn : ¬ ∃ w : Fin 13, digraph_two_overlap_counterexample_graph.Adj 9 w ∧ digraph_two_overlap_counterexample_graph.Adj 10 w := by decide exact hn h · have h := hgood 1 (by decide) have hn : ¬ ∃ w : Fin 13, digraph_two_overlap_counterexample_graph.Adj 10 w ∧ digraph_two_overlap_counterexample_graph.Adj 1 w := by decide exact hn h · have h := hgood 0 (by decide) have hn : ¬ ∃ w : Fin 13, digraph_two_overlap_counterexample_graph.Adj 11 w ∧ digraph_two_overlap_counterexample_graph.Adj 0 w := by decide exact hn h · have h := hgood 11 (by decide) have hn : ¬ ∃ w : Fin 13, digraph_two_overlap_counterexample_graph.Adj 12 w ∧ digraph_two_overlap_counterexample_graph.Adj 11 w := by decide exact hn h