digraph_two_overlap_counterexample_no_three_independent
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
- digraph_two_overlap_counterexample_graphThe explicit 13-vertex oriented digraph listed by the recorded finite counterexample.
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.
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.
intro u v unfold digraph_two_overlap_counterexample_graph infer_instance
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.
decide
- The proof of the main theorem relies on Lean's kernel computation (`decide`) to exhaustively verify all 286 triples of vertices in the 13-vertex graph.
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_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