AFTD Auto-Formalizing Theoretical Domains

digraph_two_overlap_good_center_criterion_false

theoremverified

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

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.

  1. 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.

    lines 1–5

    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
  2. 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.

    lines 7–10

    private instance in504_counterexample_decAdj : DecidableRel digraph_two_overlap_counterexample_graph.Adj := by
      intro u v
      unfold digraph_two_overlap_counterexample_graph
      infer_instance
  3. 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`).

    lines 23–24

    uses digraph_two_overlap_good_center_counterexample

      intro h
      obtain ⟨hloop, hori, hdom, hz, hnot⟩ := digraph_two_overlap_good_center_counterexample
  4. 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.

    lines 25–26

      apply hnot
      apply h digraph_two_overlap_counterexample_graph hloop hori hdom
  5. 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.

    line 27

      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.

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

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
See it in the graphDiscuss this resultChallenge it