digraph_balanced_seven_large_forces_four_cycles_conditional
A strongly connected loopless 7-outregular digraph on at least 122 vertices whose indegrees are at most seven has four disjoint directed cycles, provided every arc is dominated and every in-neighborhood contains a directed cycle.
Statement
theorem digraph_balanced_seven_large_forces_four_cycles_conditional (α : Type) [Fintype α] [DecidableEq α] [Nonempty α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (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) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) (hstrong : ∀ u v, Relation.ReflTransGen D.Adj u v) (hin : ∀ a, ∃ C : Finset α, digraph_directed_cycle_on D C ∧ ∀ v ∈ C, D.Adj v a) (hsize : 122 ≤ Fintype.card α) : ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))
- Source
- Auxiliary-graph transfer and counting steps for the OP-110 campaign.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- digraph_directed_cycle_ons is the vertex set of a directed cycle of D: its vertices can be listed without repetition, at least two of them, each with an arc to the…
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- digraph_common_predecessor_graph_connectedIn a nonempty loopless strongly connected digraph in which every arc has a common in-neighbor, the common-predecessor graph is connected.
- digraph_common_predecessor_graph_indep_free_fourIf each in-neighborhood of a finite digraph contains a directed cycle and the digraph has no four disjoint directed cycles, then its…
- digraph_common_predecessor_balanced_seven_card_le_121A 7-outregular digraph with indegrees at most seven has at most 121 vertices if its common-predecessor graph is connected and has…
The proof, explained
The proof proceeds by contradiction: suppose there are no four pairwise disjoint directed cycles in D. We consider the common predecessor graph of D, which is connected because D is strongly connected and every arc is dominated. Furthermore, because each in-neighborhood contains a directed cycle, the absence of four disjoint cycles implies that the common predecessor graph has no independent set of size 4. By an existing structural bound, such a graph can have at most 121 vertices, contradicting the assumption that the vertex count is at least 122.
Adjacency in the common predecessor graph of D is decidable.
By unfolding the definition of the common predecessor graph, two vertices are adjacent if and only if they are distinct and have a common in-neighbor in D. Since α is finite and adjacency in D is decidable, typeclass synthesis produces a decision procedure for this existential condition.
intro u v unfold digraph_common_predecessor_graph infer_instance
It suffices to derive a contradiction assuming that D contains no four pairwise disjoint directed cycles.
We enable classical logic and assume for contradiction (hno) that there is no collection of four pairwise disjoint directed cycles in D.
classical by_contra hnoThe common predecessor graph of D is connected.
Applying digraph_common_predecessor_graph_connected to the hypotheses that D is loopless (hloop), every arc is dominated (hdom), and D is strongly connected (hstrong), we conclude that the common predecessor graph is connected.
uses
digraph_common_predecessor_graph_connectedhave hc := digraph_common_predecessor_graph_connected α D hloop hdom hstrongThe common predecessor graph has no independent set of size 4.
Since every vertex has a directed cycle in its in-neighborhood (hin), any independent set of size 4 in the common predecessor graph would yield four pairwise disjoint directed cycles. By digraph_common_predecessor_graph_indep_free_four and the contradiction hypothesis (hno), the common predecessor graph is 4-independent-set-free.
uses
digraph_common_predecessor_graph_indep_free_fourhave hi := digraph_common_predecessor_graph_indep_free_four α D hin hnoThe digraph has at most 121 vertices, which contradicts the assumption that it has at least 122 vertices.
By digraph_common_predecessor_balanced_seven_card_le_121, a 7-outregular digraph with indegrees at most 7 whose common predecessor graph is connected and 4-independent-set-free has at most 121 vertices. This directly contradicts the hypothesis hsize (122 ≤ |α|), and linear integer arithmetic (omega) closes the contradiction.
uses
digraph_common_predecessor_balanced_seven_card_le_121have hb := digraph_common_predecessor_balanced_seven_card_le_121 α D hreg hinde hc hi omega
digraph_common_predecessor_graph_connected- The common predecessor graph of a loopless, strongly connected digraph in which every arc is dominated is connected.
digraph_common_predecessor_graph_indep_free_four- If every vertex has a directed cycle in its in-neighborhood and the digraph has no four pairwise disjoint directed cycles, then its common predecessor graph has no independent set of size 4.
digraph_common_predecessor_balanced_seven_card_le_121- If a digraph is 7-outregular with indegrees at most 7, and its common predecessor graph is connected and contains no independent set of size 4, then the digraph has at most 121 vertices.
- The helper instance on lines 1–4 establishes that adjacency in the common predecessor graph is decidable, a formal Lean requirement for finite set manipulation and graph properties that has no counterpart in informal mathematical writing.
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_balanced_seven_large_forces_four_cycles_conditional_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_balanced_seven_large_forces_four_cycles_conditional (α : Type) [Fintype α] [DecidableEq α] [Nonempty α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (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) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) (hstrong : ∀ u v, Relation.ReflTransGen D.Adj u v) (hin : ∀ a, ∃ C : Finset α, digraph_directed_cycle_on D C ∧ ∀ v ∈ C, D.Adj v a) (hsize : 122 ≤ Fintype.card α) : ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j)) := by classical by_contra hno have hc := digraph_common_predecessor_graph_connected α D hloop hdom hstrong have hi := digraph_common_predecessor_graph_indep_free_four α D hin hno have hb := digraph_common_predecessor_balanced_seven_card_le_121 α D hreg hinde hc hi omega