AFTD Auto-Formalizing Theoretical Domains

trianglefree24_graph_four_cycles

theoremverified

Four displayed pairwise disjoint four-vertex subsets of the explicit 24-vertex digraph are directed cycles.

Statement

theorem trianglefree24_graph_four_cycles :
    digraph_directed_cycle_on trianglefree24_graph ({0,1,2,3} : Finset (Fin 24)) ∧
    digraph_directed_cycle_on trianglefree24_graph ({4,5,6,7} : Finset (Fin 24)) ∧
    digraph_directed_cycle_on trianglefree24_graph ({8,9,10,11} : Finset (Fin 24)) ∧
    digraph_directed_cycle_on trianglefree24_graph ({12,13,14,15} : Finset (Fin 24))
Source
Explicit cycles in experiment 12544.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • trianglefree24_graphThe cyclic digraph on 24 vertices with positive modular steps 1, 4, 5, 9, 13, 17 and 21.
  • 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…

The proof, explained

To prove that each of the four disjoint 4-element sets spans a directed cycle in the 24-vertex digraph `trianglefree24_graph`, we explicitly witness each cycle with its ordered list of vertices: $[0, 1, 2, 3]$, $[4, 5, 6, 7]$, $[8, 9, 10, 11]$, and $[12, 13, 14, 15]$. In each cycle, consecutive vertices advance by $+1 \pmod{24}$ and the wrap-around step is $-3 \equiv 21 \pmod{24}$, both of which belong to the digraph's connection set $\{1, 4, 5, 9, 13, 17, 21\}$. With adjacency proven decidable, each cycle condition is verified by computational reflection via `decide`.

  1. The adjacency relation of `trianglefree24_graph` is decidable.

    For any vertices $u, v \in \text{Fin } 24$, an edge exists from $u$ to $v$ if and only if the cyclic difference $(v + 24 - u) \bmod 24$ lies in the set $\{1, 4, 5, 9, 13, 17, 21\}$. Unfolding `trianglefree24_graph` reduces the goal to membership in this explicit finite set of natural numbers, which Lean's typeclass synthesis (`infer_instance`) resolves as decidable.

    lines 4–6

      intro u v
      unfold trianglefree24_graph
      infer_instance
  2. The four vertex subsets $\{0, 1, 2, 3\}$, $\{4, 5, 6, 7\}$, $\{8, 9, 10, 11\}$, and $\{12, 13, 14, 15\}$ each span a directed cycle in `trianglefree24_graph`.

    By definition, a vertex subset spans a directed cycle if there is a duplicate-free list of vertices of length at least 2 whose elements equal the subset, such that consecutive elements form directed edges and the last element connects back to the first. We supply the witness lists $[0, 1, 2, 3]$, $[4, 5, 6, 7]$, $[8, 9, 10, 11]$, and $[12, 13, 14, 15]$ for each of the four conjunctions. In each list, consecutive vertices advance by $+1 \pmod{24}$ and the closing step is $-3 \equiv 21 \pmod{24}$. Since both $1$ and $21$ are in the connection set $\{1, 4, 5, 9, 13, 17, 21\}$, all edges exist. The `decide` tactic evaluates and closes each of the four subgoals by direct computation.

    lines 13–14

      exact ⟨⟨[0,1,2,3], by decide⟩, ⟨[4,5,6,7], by decide⟩,
        ⟨[8,9,10,11], by decide⟩, ⟨[12,13,14,15], by decide⟩⟩

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

set_option maxRecDepth 200000set_option maxHeartbeats 0private instance trianglefree24_decAdj_four_cycles : DecidableRel trianglefree24_graph.Adj := by  intro u v  unfold trianglefree24_graph  infer_instancetheorem trianglefree24_graph_four_cycles :    digraph_directed_cycle_on trianglefree24_graph ({0,1,2,3} : Finset (Fin 24)) ∧    digraph_directed_cycle_on trianglefree24_graph ({4,5,6,7} : Finset (Fin 24)) ∧    digraph_directed_cycle_on trianglefree24_graph ({8,9,10,11} : Finset (Fin 24)) ∧    digraph_directed_cycle_on trianglefree24_graph ({12,13,14,15} : Finset (Fin 24)) := by  exact ⟨⟨[0,1,2,3], by decide⟩, ⟨[4,5,6,7], by decide⟩,    ⟨[8,9,10,11], by decide⟩, ⟨[12,13,14,15], by decide⟩⟩
See it in the graphDiscuss this resultChallenge it