trianglefree24_graph_four_cycles
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`.
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.
intro u v unfold trianglefree24_graph infer_instance
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.
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⟩⟩
- The helper instance `trianglefree24_decAdj_four_cycles` (lines 3–6) registers the decidability of adjacency in `trianglefree24_graph`, which allows Lean to evaluate cycle properties computationally.
- All conditions defining the directed cycles (no duplicate vertices, length at least 2, matching vertex sets, and existence of forward and return edges) are verified entirely by computational reflection (`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
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.
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⟩⟩