AFTD Auto-Formalizing Theoretical Domains

cycle_graph_eight_strong_orientation_diameter_le_seven

theoremverified

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.

  1. 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.

    lines 6–8

    uses cycle_graph_eight_strong_orientation_diameter_le_seven_digraph

      intro u v
      dsimp [cycle_graph_eight_strong_orientation_diameter_le_seven_digraph]
      infer_instance
  2. 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.

    lines 13–16

      induction k generalizing u v with
      | zero =>
        change Decidable (u = v)
        infer_instance
  3. 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.

    lines 17–26

    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_instance
  4. The 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.

    lines 30–31

    uses cycle_graph_eight_strong_orientation_diameter_le_seven_digraph, is_graph_orientation

      use 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

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

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⟩
See it in the graphDiscuss this resultChallenge it