digraph_safe17_structure
The displayed graph is oriented and seven-diregular, and every two distinct vertices have a common predecessor.
Statement
theorem digraph_safe17_structure : (∀ u, ¬ digraph_safe17_graph.Adj u u) ∧ (∀ u v, digraph_safe17_graph.Adj u v → ¬ digraph_safe17_graph.Adj v u) ∧ (∀ u, (Finset.univ.filter fun v => digraph_safe17_graph.Adj u v).card = 7) ∧ (∀ v, (Finset.univ.filter fun u => digraph_safe17_graph.Adj u v).card = 7) ∧ (∀ u v, u ≠ v → ∃ p, digraph_safe17_graph.Adj p u ∧ digraph_safe17_graph.Adj p v)
- 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 4
- digraph_safe_cycle_universal_criterion_falseIt is false that every loopless oriented seven-diregular graph on seventeen vertices with a complete common-predecessor graph contains a…
- digraph_safe17_two_cycle_impossibleThe displayed oriented graph has no directed cycle on two vertices.
- digraph_safe17_no_long_safe_setEvery proper set of at least five vertices in the displayed graph has an outside vertex with at least three outneighbors in the set.
- digraph_safe17_every_proper_cycle_unsafeEvery proper directed cycle in the displayed seventeen-vertex graph has an outside vertex with at least three outneighbors on it.
The proof, explained
The theorem establishes five structural properties of a directed graph on 17 vertices: it has no self-loops, contains no 2-cycles (is an oriented graph), is 7-diregular (each in-degree and out-degree is 7), and any two distinct vertices share a common predecessor. Decidability of the adjacency relation is first registered as an instance, after which the entire statement is verified by finite exhaustive computation via the `decide` tactic.
Adjacency between any two vertices in the graph is decidable.
For any two vertices $u$ and $v$ in $\mathrm{Fin}\; 17$, unfolding the definition of the graph reveals that adjacency is defined by whether $(v - u) \in \{1, 2, 3, 5, 6, 7, 13\}$. Membership in this explicit finite set of natural numbers is decidable by standard typeclass resolution.
intro u v unfold digraph_safe17_graph infer_instance
The graph is loopless, asymmetric, 7-out-regular, 7-in-regular, and every pair of distinct vertices shares a common predecessor. automation
Because $\mathrm{Fin}\; 17$ is a finite type and the adjacency relation was shown to be decidable, the entire conjunction of universally and existentially quantified statements is decidable. The `decide` tactic evaluates the proposition to true by finite exhaustive computation.
decide
- The proof relies on Lean's `decide` tactic to establish the theorem by exhaustive finite computation over the 17 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
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_0 : DecidableRel digraph_safe17_graph.Adj := by intro u v unfold digraph_safe17_graph infer_instancetheorem digraph_safe17_structure : (∀ u, ¬ digraph_safe17_graph.Adj u u) ∧ (∀ u v, digraph_safe17_graph.Adj u v → ¬ digraph_safe17_graph.Adj v u) ∧ (∀ u, (Finset.univ.filter fun v => digraph_safe17_graph.Adj u v).card = 7) ∧ (∀ v, (Finset.univ.filter fun u => digraph_safe17_graph.Adj u v).card = 7) ∧ (∀ u v, u ≠ v → ∃ p, digraph_safe17_graph.Adj p u ∧ digraph_safe17_graph.Adj p v) := by decide