AFTD Auto-Formalizing Theoretical Domains

digraph_two_overlap_good_center_counterexample

theoremverified

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
Used by 1

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.

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

    lines 2–4

      intro u v
      unfold digraph_two_overlap_counterexample_graph
      infer_instance
  2. 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.

    lines 7–9

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  3. 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.

    lines 26–27

      constructor
      · decide
  4. 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.

    lines 28–29

      constructor
      · decide
  5. 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.

    lines 30–31

      constructor
      · decide
  6. 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.

    lines 32–33

      constructor
      · decide
  7. 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.

    lines 34–36

      ·
        rintro ⟨u, hclean, hgood⟩
        fin_cases u
  8. Vertices 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.

    lines 37–50

        · 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
  9. 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.

    lines 51–68

        · 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

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