digraph_common_predecessor_graph_129_contradiction
No digraph on 129 vertices can have outdegree at most seven while its common-predecessor graph is connected and has no independent set of size four.
Statement
theorem digraph_common_predecessor_graph_129_contradiction (D : Digraph (Fin 129)) [DecidableRel D.Adj] (hdeg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card ≤ 7) (hconn : (digraph_common_predecessor_graph D).Connected) (hindep : (digraph_common_predecessor_graph D).IndepSetFree 4) : False
- Source
- The final auxiliary-graph counting step toward the 128-vertex minimum-counterexample bound for OP-110.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- digraph_common_predecessor_graph_edge_count_leIf every vertex of a finite digraph has at most seven out-neighbors, then its common-predecessor graph has at most 21 times as many edges…
- connected_graph_129_independence_three_edge_boundEvery connected simple graph on 129 vertices with no independent set of size four has at least 2710 edges.
The proof, explained
The proof derives a contradiction by sandwiching the edge count of the common-predecessor graph between contradictory lower and upper bounds. Because the common-predecessor graph is connected on 129 vertices with independence number at most 3, it must have at least 2710 edges by an edge-extremal bound. On the other hand, the outdegree restriction of at most 7 implies that each vertex can generate at most 21 pairs of successors, yielding an upper bound of 21 × 129 = 2709 edges. Linear arithmetic finishes the proof by observing 2710 ≤ 2709 is impossible.
Adjacency in the common-predecessor graph is decidable.
For any two vertices $u$ and $v$, adjacency in the common-predecessor graph means $u \ne v$ and there exists a common predecessor $w$ with directed edges to both $u$ and $v$. Since the vertex set is finite and adjacency in $D$ is decidable, typeclass inference automatically synthesizes decidability for this bounded existential condition.
intro u v unfold digraph_common_predecessor_graph infer_instance
The common-predecessor graph has at least 2710 edges.
By `connected_graph_129_independence_three_edge_bound`, any connected graph on 129 vertices with independence number at most 3 (no independent set of size 4) has at least 2710 edges. Applying this lemma to the common-predecessor graph with hypotheses `hconn` and `hindep` yields the lower bound.
uses
connected_graph_129_independence_three_edge_boundhave hlow := connected_graph_129_independence_three_edge_bound (digraph_common_predecessor_graph D) hconn hindepThe common-predecessor graph has at most 2709 edges.
By `digraph_common_predecessor_graph_edge_count_le`, since each vertex in $D$ has outdegree at most 7, the common-predecessor graph has at most $21 \\times |V| = 21 \\times 129$ edges. Normalizing this numerical expression (`norm_num`) evaluates $21 \\times 129$ to 2709.
uses
digraph_common_predecessor_graph_edge_count_lehave hupper := digraph_common_predecessor_graph_edge_count_le (Fin 129) D hdeg norm_num at hupper
A contradiction is reached. automation
Linear integer arithmetic (`omega`) detects the contradiction between the lower bound of 2710 edges and the upper bound of 2709 edges, closing the goal.
omega
connected_graph_129_independence_three_edge_bound- Any connected simple graph on 129 vertices with no independent set of size 4 has at least 2710 edges.
digraph_common_predecessor_graph_edge_count_le- For any finite directed graph whose vertices have outdegree at most 7, the number of edges in its common-predecessor graph is at most 21 times the number of vertices.
- Lines 1–5 establish decidability of adjacency in the common-predecessor graph via typeclass inference. This is a formal Lean requirement enabling the edge set to be treated as a finite set (`edgeFinset`), with no mathematical counterpart on paper.
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 {α : 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_instancetheorem digraph_common_predecessor_graph_129_contradiction (D : Digraph (Fin 129)) [DecidableRel D.Adj] (hdeg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card ≤ 7) (hconn : (digraph_common_predecessor_graph D).Connected) (hindep : (digraph_common_predecessor_graph D).IndepSetFree 4) : False := by have hlow := connected_graph_129_independence_three_edge_bound (digraph_common_predecessor_graph D) hconn hindep have hupper := digraph_common_predecessor_graph_edge_count_le (Fin 129) D hdeg norm_num at hupper omega