digraph_common_predecessor_balanced_seven_card_le_121
A 7-outregular digraph with indegrees at most seven has at most 121 vertices if its common-predecessor graph is connected and has independence number at most three.
Statement
theorem digraph_common_predecessor_balanced_seven_card_le_121 (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7) (hinde : ∀ v, (Finset.univ.filter fun w => D.Adj w v).card ≤ 7) (hconn : (digraph_common_predecessor_graph D).Connected) (hindep : (digraph_common_predecessor_graph D).IndepSetFree 4) : Fintype.card α ≤ 121
- Source
- Auxiliary-graph transfer and counting steps for the OP-110 campaign.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- digraph_common_predecessor_seven_bounded_indegree_degree_boundIf all outdegrees equal seven and all indegrees are at most seven, every vertex of the common-predecessor graph has degree at most 42.
- digraph_common_predecessor_edges_seven_cliqueIn a 7-outregular finite digraph, every edge of its common-predecessor graph lies in a clique of exactly seven vertices.
- connected_graph_indep_three_degree_42_seven_cliques_card_le_121A connected finite simple graph with independence number at most three, maximum degree at most 42, and every edge in a seven-vertex clique…
- Used by 1
- digraph_balanced_seven_large_forces_four_cycles_conditionalA strongly connected loopless 7-outregular digraph on at least 122 vertices whose indegrees are at most seven has four disjoint directed…
The proof, explained
The proof reduces the vertex bound to an established result for simple graphs, `connected_graph_indep_three_degree_42_seven_cliques_card_le_121`, applied to the common-predecessor graph of the digraph D. In this graph, two vertices are adjacent if they share an in-neighbor; because D is 7-outregular with indegrees at most 7, each vertex has degree at most 42, and each edge is contained in the 7-clique formed by the out-neighbors of their shared predecessor. Since the common-predecessor graph is connected and has independence number at most 3, the general bound immediately yields that the digraph has at most 121 vertices.
Adjacency in the common-predecessor graph of D is decidable. automation
For any vertices u and v, unfolding the definition of the common-predecessor graph gives the condition u ≠ v ∧ ∃ w, D.Adj w u ∧ D.Adj w v. Since the vertex set is finite and both equality and digraph adjacency are decidable, typeclass inference (`infer_instance`) automatically synthesizes decidability for this bounded existential formula.
intro u v unfold digraph_common_predecessor_graph infer_instance
The digraph has at most 121 vertices (|α| ≤ 121).
We apply the general theorem `connected_graph_indep_three_degree_42_seven_cliques_card_le_121` to the common-predecessor graph of D. Connectedness (`hconn`) and independence number at most 3 (`hindep`) are given as assumptions. The maximum degree bound of 42 is provided by `digraph_common_predecessor_seven_bounded_indegree_degree_bound`, and the property that every edge lies in a 7-clique is provided by `digraph_common_predecessor_edges_seven_clique`. Together, these hypotheses imply that |α| ≤ 121.
uses
connected_graph_indep_three_degree_42_seven_cliques_card_le_121,digraph_common_predecessor_seven_bounded_indegree_degree_bound,digraph_common_predecessor_edges_seven_cliqueexact connected_graph_indep_three_degree_42_seven_cliques_card_le_121 α (digraph_common_predecessor_graph D) hconn hindep (digraph_common_predecessor_seven_bounded_indegree_degree_bound α D hreg hinde) (digraph_common_predecessor_edges_seven_clique α D hreg)
connected_graph_indep_three_degree_42_seven_cliques_card_le_121- A connected graph with independence number at most 3, maximum degree at most 42, and every edge contained in a 7-clique has at most 121 vertices.
digraph_common_predecessor_seven_bounded_indegree_degree_bound- In a 7-outregular digraph with indegrees at most 7, every vertex in the common-predecessor graph has degree at most 42.
digraph_common_predecessor_edges_seven_clique- In a 7-outregular digraph, every edge of the common-predecessor graph is contained in a 7-clique formed by the out-neighborhood of their common predecessor.
- The auxiliary instance on lines 1–4 provides decidability of adjacency for the common-predecessor graph, which is a formal typeclass requirement for Lean's graph definitions (such as degree and clique calculations) that is mathematically routine for finite graphs.
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 in478_digraph_common_predecessor_balanced_seven_card_le_121_decAdj {α : 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_balanced_seven_card_le_121 (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7) (hinde : ∀ v, (Finset.univ.filter fun w => D.Adj w v).card ≤ 7) (hconn : (digraph_common_predecessor_graph D).Connected) (hindep : (digraph_common_predecessor_graph D).IndepSetFree 4) : Fintype.card α ≤ 121 := by exact connected_graph_indep_three_degree_42_seven_cliques_card_le_121 α (digraph_common_predecessor_graph D) hconn hindep (digraph_common_predecessor_seven_bounded_indegree_degree_bound α D hreg hinde) (digraph_common_predecessor_edges_seven_clique α D hreg)