digraph_two_overlap_good_center_criterion_false
It is false that every oriented arc-dominated loopless digraph on thirteen vertices with twice its common-predecessor overlap below thirteen has a vertex with a clean out-neighborhood whose outgoing arcs all have common successors.
Statement
theorem digraph_two_overlap_good_center_criterion_false : ¬ ∀ (D : Digraph (Fin 13)) [DecidableRel D.Adj], (∀ u, ¬ D.Adj u u) → (∀ u v, D.Adj u v → ¬ D.Adj v u) → (∀ u v, D.Adj u v → ∃ p, D.Adj p u ∧ D.Adj p v) → 2 * ((∑ u : Fin 13, Nat.choose (Finset.univ.filter fun v => D.Adj u v).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card (Fin 13) → ∃ u : Fin 13, (∀ a b, a ≠ b → D.Adj u a → D.Adj u b → ∀ p, D.Adj p a → D.Adj p b → p = u) ∧ (∀ v, D.Adj u v → ∃ w, D.Adj u w ∧ D.Adj v w)
- Source
- Refutation of a stronger 2z good-center route for OP-110, using the explicit counterexample from experiments 13185 and 13186.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- digraph_two_overlap_counterexample_graphThe explicit 13-vertex oriented digraph listed by the recorded finite counterexample.
- digraph_two_overlap_good_center_counterexampleThe displayed thirteen-vertex graph is loopless, oriented and arc-dominated, has common-predecessor overlap six, and has no vertex whose…
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
The proof, explained
The theorem disproves the proposed criterion by contradiction, using the explicit 13-vertex counterexample digraph `digraph_two_overlap_counterexample_graph`. Assuming the universal statement holds, we apply it to this digraph. The pre-proven lemma `digraph_two_overlap_good_center_counterexample` establishes that the graph is loopless, oriented, arc-dominated, and has no good center vertex. The remaining condition that twice the overlap difference is strictly less than 13 reduces to the true numerical inequality 12 < 13, which is verified by finite computation.
Adjacency in the common-predecessor graph of any finite digraph with decidable adjacency is decidable.
Unfolding the definition of the common-predecessor graph, two vertices u and v are adjacent if and only if u ≠ v and there exists a vertex w that precedes both u and v. Because the vertex set is finite and equality as well as adjacency in D are decidable, this bounded existential search is decidable by typeclass synthesis.
private instance in504_all_graph_decAdj {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] : DecidableRel (digraph_common_predecessor_graph D).Adj := by intro u v unfold digraph_common_predecessor_graph infer_instance
Adjacency in the counterexample digraph is decidable.
Unfolding `digraph_two_overlap_counterexample_graph`, adjacency is defined as membership in an explicit list of 45 pairs of vertices in Fin 13 × Fin 13, which is decidable by typeclass synthesis.
private instance in504_counterexample_decAdj : DecidableRel digraph_two_overlap_counterexample_graph.Adj := by intro u v unfold digraph_two_overlap_counterexample_graph infer_instance
Assume the universal claim holds, and instantiate the properties of the counterexample digraph.
We assume for contradiction that the criterion holds for every 13-vertex digraph (hypothesis h). We then obtain the properties of the explicit 13-vertex counterexample digraph from `digraph_two_overlap_good_center_counterexample`: it is loopless (`hloop`), oriented (`hori`), arc-dominated (`hdom`), has overlap difference 6 (`hz`), and contains no good center vertex (`hnot`).
uses
digraph_two_overlap_good_center_counterexampleintro h obtain ⟨hloop, hori, hdom, hz, hnot⟩ := digraph_two_overlap_good_center_counterexample
It suffices to verify that the counterexample digraph satisfies the overlap inequality.
Since `hnot` asserts that no good center vertex exists in the counterexample digraph, applying `hnot` reduces the goal to showing that such a vertex does exist. Applying the assumed universal statement h to the counterexample digraph along with its verified loopless, oriented, and dominated properties leaves only the condition that twice its overlap difference is strictly less than 13.
apply hnot apply h digraph_two_overlap_counterexample_graph hloop hori hdom
The counterexample digraph satisfies the overlap inequality, completing the proof. automation
The required condition 2 * ((∑ u, Nat.choose (out-degree of u) 2) - |E(common predecessor graph)|) < 13 evaluates to 2 * 6 < 13 (that is, 12 < 13), which `decide` verifies by direct computation on the finite graph.
decide
digraph_two_overlap_good_center_counterexample- The explicit 13-vertex digraph `digraph_two_overlap_counterexample_graph` is loopless, oriented, arc-dominated, has overlap difference equal to 6, and does not have any vertex with a clean out-neighborhood whose outgoing arcs all share common successors.
- The final arithmetic check 2 * 6 < 13 is closed automatically by `decide`, which relies on the decidability instances established in lines 1–10 to evaluate graph adjacency and edge sets.
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_all_graph_decAdj {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] : DecidableRel (digraph_common_predecessor_graph D).Adj := by intro u v unfold digraph_common_predecessor_graph infer_instanceprivate instance in504_counterexample_decAdj : DecidableRel digraph_two_overlap_counterexample_graph.Adj := by intro u v unfold digraph_two_overlap_counterexample_graph infer_instancetheorem digraph_two_overlap_good_center_criterion_false : ¬ ∀ (D : Digraph (Fin 13)) [DecidableRel D.Adj], (∀ u, ¬ D.Adj u u) → (∀ u v, D.Adj u v → ¬ D.Adj v u) → (∀ u v, D.Adj u v → ∃ p, D.Adj p u ∧ D.Adj p v) → 2 * ((∑ u : Fin 13, Nat.choose (Finset.univ.filter fun v => D.Adj u v).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card (Fin 13) → ∃ u : Fin 13, (∀ a b, a ≠ b → D.Adj u a → D.Adj u b → ∀ p, D.Adj p a → D.Adj p b → p = u) ∧ (∀ v, D.Adj u v → ∃ w, D.Adj u w ∧ D.Adj v w) := by intro h obtain ⟨hloop, hori, hdom, hz, hnot⟩ := digraph_two_overlap_good_center_counterexample apply hnot apply h digraph_two_overlap_counterexample_graph hloop hori hdom decide