AFTD Auto-Formalizing Theoretical Domains

digraph_two_overlap_counterexample_no_three_independent

theoremverified

In the displayed thirteen-vertex counterexample, among any three distinct vertices some pair has a common predecessor; equivalently the auxiliary graph has independence number at most two.

Statement

theorem digraph_two_overlap_counterexample_no_three_independent :
    ∀ a b c : Fin 13, a ≠ b → a ≠ c → b ≠ c →
      (∃ p, digraph_two_overlap_counterexample_graph.Adj p a ∧ digraph_two_overlap_counterexample_graph.Adj p b) ∨
      (∃ p, digraph_two_overlap_counterexample_graph.Adj p a ∧ digraph_two_overlap_counterexample_graph.Adj p c) ∨
      (∃ p, digraph_two_overlap_counterexample_graph.Adj p b ∧ digraph_two_overlap_counterexample_graph.Adj p c)
Source
Finite verification of the auxiliary independence obstruction to the 2z good-center route for OP-110; experiment 13207.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The theorem asserts that in the given 13-vertex directed graph, no three distinct vertices are independent in the auxiliary graph of common predecessors—that is, every triple contains a pair with a common in-neighbour. First, the edge relation is proven decidable by reducing it to membership in an explicit finite set of pairs. Then, because the graph is finite and adjacency is decidable, the theorem is proved by exhaustive computation over all triples of vertices using the `decide` tactic.

  1. Adjacency in the 13-vertex directed graph is decidable. automation

    To prove that adjacency is decidable for any two vertices $u$ and $v$ (introduced by `intro u v`), the definition of `digraph_two_overlap_counterexample_graph` is unfolded. Adjacency reduces to membership of the pair $(u, v)$ in an explicit finite set of 45 edges (`Finset`), which typeclass resolution (`infer_instance`) automatically decides.

    lines 2–4

      intro u v
      unfold digraph_two_overlap_counterexample_graph
      infer_instance
  2. Among any three distinct vertices, at least one pair has a common predecessor. automation

    The goal is a universal statement over all distinct triples $a, b, c \\in \\mathrm{Fin}\\; 13$, asserting that there exists some vertex $p$ with directed edges to at least two of them. Because the vertex type is finite and adjacency was shown to be decidable, the proposition is decidable by bounded search. The `decide` tactic checks the condition by exhaustive computation over all $\\binom{13}{3} = 286$ vertex triples.

    line 11

      decide

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_independence_decAdj : DecidableRel digraph_two_overlap_counterexample_graph.Adj := by  intro u v  unfold digraph_two_overlap_counterexample_graph  infer_instancetheorem digraph_two_overlap_counterexample_no_three_independent :    ∀ a b c : Fin 13, a ≠ b → a ≠ c → b ≠ c →      (∃ p, digraph_two_overlap_counterexample_graph.Adj p a ∧ digraph_two_overlap_counterexample_graph.Adj p b) ∨      (∃ p, digraph_two_overlap_counterexample_graph.Adj p a ∧ digraph_two_overlap_counterexample_graph.Adj p c) ∨      (∃ p, digraph_two_overlap_counterexample_graph.Adj p b ∧ digraph_two_overlap_counterexample_graph.Adj p c) := by  decide
See it in the graphDiscuss this resultChallenge it