cycle_graph_eight_strong_orientation_diameter_le_seven
Sanity (non-vacuity): the 8-cycle, a bridgeless graph of diameter 4, has a strong orientation of directed diameter at most 7, namely the cyclic orientation.
Statement
theorem cycle_graph_eight_strong_orientation_diameter_le_seven :
has_strong_orientation_of_diameter_le (SimpleGraph.cycleGraph 8) 7- Source
- sanity lemma for has_strong_orientation_of_diameter_le (OP-119)
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- has_strong_orientation_of_diameter_leThe simple graph G has an orientation D (each edge of G gets exactly one direction, no other arcs) in which every ordered pair of vertices…
- digraph_reach_withindigraph_reach_within D k u v: there is a directed walk of length at most k from u to v in the digraph D (equivalently, the directed…
- is_graph_orientationA digraph D is an orientation of a simple graph G if every edge of G is assigned exactly one direction in D, and non-adjacent pairs in G…
The proof, explained
To show that the 8-cycle has a strong orientation with directed diameter at most 7, the proof chooses the standard cyclic orientation, where edges are directed from u to u + 1 (mod 8). To enable mechanical verification, decidability of adjacency and bounded-step reachability are first established by induction on the step bound. The proof then concludes by delegating both the orientation condition and the diameter bound to exhaustive finite computation via `decide` over Fin 8.
Adjacency in the cyclic directed graph on Fin 8 is decidable.
Unfolding the definition of `cycle_graph_eight_strong_orientation_diameter_le_seven_digraph`, an edge from u to v exists if and only if v - u = 1 in Fin 8. Equality in the finite type Fin 8 is decidable, so typeclass synthesis (`infer_instance`) provides the decision procedure.
uses
cycle_graph_eight_strong_orientation_diameter_le_seven_digraphintro u v dsimp [cycle_graph_eight_strong_orientation_diameter_le_seven_digraph] infer_instance
Base case: reachability within 0 steps is decidable for any pair of vertices.
We proceed by induction on the step bound k. When k = 0, reachability within 0 steps is definitionally equality u = v, which is decidable on Fin 8 by typeclass synthesis.
induction k generalizing u v with | zero => change Decidable (u = v) infer_instance
Inductive step: reachability within k + 1 steps is decidable for any pair of vertices.
Reachability within k + 1 steps is defined as reachability within k steps or the existence of an intermediate vertex w adjacent to u from which v is reachable in k steps. For each w, this conjunction is decidable because adjacency is decidable and k-step reachability is decidable by the induction hypothesis. Since Fin 8 is a finite type, the existential quantification over w and the disjunction are decidable by typeclass synthesis.
uses
inferInstance| succ k ih => change Decidable (digraph_reach_within cycle_graph_eight_strong_orientation_diameter_le_seven_digraph k u v ∨ ∃ w, cycle_graph_eight_strong_orientation_diameter_le_seven_digraph.Adj u w ∧ digraph_reach_within cycle_graph_eight_strong_orientation_diameter_le_seven_digraph k w v) have : ∀ w, Decidable (cycle_graph_eight_strong_orientation_diameter_le_seven_digraph.Adj u w ∧ digraph_reach_within cycle_graph_eight_strong_orientation_diameter_le_seven_digraph k w v) := fun w => by have : Decidable (cycle_graph_eight_strong_orientation_diameter_le_seven_digraph.Adj u w) := inferInstance have : Decidable (digraph_reach_within cycle_graph_eight_strong_orientation_diameter_le_seven_digraph k w v) := ih w v infer_instance infer_instanceThe cyclic digraph is an orientation of the 8-cycle and has directed diameter at most 7, completing the proof. automation
We provide the cyclic digraph `cycle_graph_eight_strong_orientation_diameter_le_seven_digraph` as the witness orientation. Unfolding `is_graph_orientation`, this leaves two obligations: verifying that the directed edges correctly orient `SimpleGraph.cycleGraph 8`, and checking that every vertex can reach every other vertex within 7 steps. Because all involved relations are decidable and the vertex set Fin 8 is finite, Lean's `decide` tactic discharges both goals by exhaustive computation.
uses
cycle_graph_eight_strong_orientation_diameter_le_seven_digraph,is_graph_orientationuse cycle_graph_eight_strong_orientation_diameter_le_seven_digraph refine ⟨by dsimp [is_graph_orientation]; decide, by decide⟩
cycle_graph_eight_strong_orientation_diameter_le_seven_digraph- the directed graph on vertices `Fin 8` where an edge from u to v exists if and only if v - u = 1
inferInstance- synthesizes and returns a typeclass instance available in the current context
is_graph_orientation- a directed graph D is an orientation of an undirected graph G if between any two vertices, an edge exists in G if and only if exactly one directed edge exists in D
- The two instance declarations in lines 4–26 set up computability (decidability) for adjacency and reachability. In a paper proof, relations on a finite set are trivially decidable, but Lean requires explicit `Decidable` typeclass instances before the `decide` tactic can evaluate the graph properties.
- In line 31, `decide` proves that the digraph is an orientation and has directed diameter at most 7 by exhaustively checking all pairs of vertices in `Fin 8` via computation, without generating human-readable intermediate proof steps.
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.
def cycle_graph_eight_strong_orientation_diameter_le_seven_digraph : Digraph (Fin 8) where Adj u v := v - u = 1instance cycle_graph_eight_strong_orientation_diameter_le_seven_adj_decidable : DecidableRel cycle_graph_eight_strong_orientation_diameter_le_seven_digraph.Adj := by intro u v dsimp [cycle_graph_eight_strong_orientation_diameter_le_seven_digraph] infer_instanceinstance cycle_graph_eight_strong_orientation_diameter_le_seven_reach_decidable (k : ℕ) (u v : Fin 8) : Decidable (digraph_reach_within cycle_graph_eight_strong_orientation_diameter_le_seven_digraph k u v) := by induction k generalizing u v with | zero => change Decidable (u = v) infer_instance | succ k ih => change Decidable (digraph_reach_within cycle_graph_eight_strong_orientation_diameter_le_seven_digraph k u v ∨ ∃ w, cycle_graph_eight_strong_orientation_diameter_le_seven_digraph.Adj u w ∧ digraph_reach_within cycle_graph_eight_strong_orientation_diameter_le_seven_digraph k w v) have : ∀ w, Decidable (cycle_graph_eight_strong_orientation_diameter_le_seven_digraph.Adj u w ∧ digraph_reach_within cycle_graph_eight_strong_orientation_diameter_le_seven_digraph k w v) := fun w => by have : Decidable (cycle_graph_eight_strong_orientation_diameter_le_seven_digraph.Adj u w) := inferInstance have : Decidable (digraph_reach_within cycle_graph_eight_strong_orientation_diameter_le_seven_digraph k w v) := ih w v infer_instance infer_instancetheorem cycle_graph_eight_strong_orientation_diameter_le_seven : has_strong_orientation_of_diameter_le (SimpleGraph.cycleGraph 8) 7 := by use cycle_graph_eight_strong_orientation_diameter_le_seven_digraph refine ⟨by dsimp [is_graph_orientation]; decide, by decide⟩