AFTD Auto-Formalizing Theoretical Domains

digraph_balanced_seven_large_forces_four_cycles_conditional

theoremverified

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

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.

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

    lines 2–4

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

    lines 17–18

      classical
      by_contra hno
  3. The 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.

    line 19

    uses digraph_common_predecessor_graph_connected

      have hc := digraph_common_predecessor_graph_connected α D hloop hdom hstrong
  4. The 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.

    line 20

    uses digraph_common_predecessor_graph_indep_free_four

      have hi := digraph_common_predecessor_graph_indep_free_four α D hin hno
  5. The 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.

    lines 21–22

    uses digraph_common_predecessor_balanced_seven_card_le_121

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

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