digraph_safe17_rooted_four_unsafe
Every directed four-cycle through zero in the displayed graph has an outside vertex pointing to at least three of its vertices.
Statement
theorem digraph_safe17_rooted_four_unsafe :
∀ a b c : Fin 17,
digraph_safe17_graph.Adj 0 a → digraph_safe17_graph.Adj a b →
digraph_safe17_graph.Adj b c → digraph_safe17_graph.Adj c 0 →
∃ x : Fin 17, x ≠ 0 ∧ x ≠ a ∧ x ≠ b ∧ x ≠ c ∧
((digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x a ∧
digraph_safe17_graph.Adj x b) ∨
(digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x a ∧
digraph_safe17_graph.Adj x c) ∨
(digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x b ∧
digraph_safe17_graph.Adj x c) ∨
(digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b ∧
digraph_safe17_graph.Adj x c))- Source
- Finite safe-cycle obstruction for OP-110; experiment 13260.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_safe17_graphThe seventeen-vertex cyclic digraph with the displayed seven out-steps.
- Used by 1
- digraph_safe17_four_unsafeEvery directed four-cycle in the displayed graph has an outside vertex pointing to at least three of its vertices.
The proof, explained
The theorem is proved by finite computational exhaustion. Adjacency in the 17-vertex Cayley digraph is first established to be decidable. Because the vertex set Fin 17 is finite, the statement that every directed four-cycle through 0 is dominated at three or more vertices by an outside vertex is a decidable proposition, which Lean verifies by exhaustive evaluation using the `decide` tactic.
The adjacency relation of digraph_safe17_graph is decidable.
For any two vertices u and v, the graph definition is unfolded to express adjacency as (v - u).val ∈ {1, 2, 3, 5, 6, 7, 13}. Since membership in this explicit finite set of natural numbers is decidable, typeclass inference (`infer_instance`) automatically synthesises the decidability instance.
intro u v unfold digraph_safe17_graph infer_instance
Every directed four-cycle through 0 has an outside vertex pointing to at least three of its vertices. automation
The theorem is a first-order sentence whose quantifiers range over Fin 17, a finite type with 17 elements. Because the adjacency relation is decidable, the entire formula is a decidable proposition. Lean's `decide` tactic evaluates this proposition by exhaustively checking all candidate four-cycles through 0 and verifying that each admits an outside vertex pointing to at least three vertices of the cycle.
uses
in504_safe17_decAdj_2decide
in504_safe17_decAdj_2- For any two vertices u and v in Fin 17, it is decidable whether there is a directed edge from u to v in digraph_safe17_graph.
- The main theorem is proved entirely by automation via the `decide` tactic, which evaluates the proposition by exhaustive finite search over all elements of Fin 17 without producing a traditional paper proof.
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 in504_safe17_decAdj_2 : DecidableRel digraph_safe17_graph.Adj := by intro u v unfold digraph_safe17_graph infer_instancetheorem digraph_safe17_rooted_four_unsafe : ∀ a b c : Fin 17, digraph_safe17_graph.Adj 0 a → digraph_safe17_graph.Adj a b → digraph_safe17_graph.Adj b c → digraph_safe17_graph.Adj c 0 → ∃ x : Fin 17, x ≠ 0 ∧ x ≠ a ∧ x ≠ b ∧ x ≠ c ∧ ((digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b) ∨ (digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x c) ∨ (digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x b ∧ digraph_safe17_graph.Adj x c) ∨ (digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b ∧ digraph_safe17_graph.Adj x c)) := by decide