AFTD Auto-Formalizing Theoretical Domains

digraph_common_predecessor_graph_129_contradiction

theoremverified

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

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.

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

    lines 3–5

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

    lines 12–13

    uses connected_graph_129_independence_three_edge_bound

      have hlow := connected_graph_129_independence_three_edge_bound
        (digraph_common_predecessor_graph D) hconn hindep
  3. The 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.

    lines 14–15

    uses digraph_common_predecessor_graph_edge_count_le

      have hupper := digraph_common_predecessor_graph_edge_count_le (Fin 129) D hdeg
      norm_num at hupper
  4. 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.

    line 16

      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.

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