AFTD Auto-Formalizing Theoretical Domains

exists_non_circulant_sharp_cyclic_graph_order_eight

theoremverifiedoriginal

There exists a simple graph G on ZMod 8 with at least one edge that admits a sharp cyclic labeling and is not a circulant graph on ZMod 8.

Statement

theorem exists_non_circulant_sharp_cyclic_graph_order_eight :
    ∃ (G : SimpleGraph (ZMod 8)) (_ : DecidableRel G.Adj),
      (∃ u v, G.Adj u v) ∧ admits_sharp_cyclic_labeling 8 G ∧ ¬ is_circulant_graph 8 G
Related work
arXiv:2610.31807 Question 12.1
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

Read back from the Lean

There exists a simple graph $G$ on the vertex set $\mathbb{Z}/8\mathbb{Z}$ equipped with a decidability instance for its adjacency relation such that: 1. $G$ has at least one edge (there exist vertices $u, v \in \mathbb{Z}/8\mathbb{Z}$ such that $G\text{.Adj } u\ v$); 2. $G$ admits a sharp cyclic labeling of order 8; and 3. $G$ is not a circulant graph of order 8 (it is not isomorphic to any circulant graph on $\mathbb{Z}/8\mathbb{Z}$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem is established by providing an explicit witness: a Hankel-type graph on ZMod 8 where vertices x and y are adjacent if and only if (x + y).val ∈ {1, 3, 5}. Symmetry is immediate from the commutativity of addition in ZMod 8, while looplessness holds because 2x mod 8 is always even and thus never 1, 3, or 5. The graph has at least one edge (such as {0, 1}), and two existing theorems confirm that it admits a sharp cyclic labeling and is not a circulant graph.

  1. The Hankel-type adjacency relation on ZMod 8, defined by x ~ y iff (x + y).val ∈ {1, 3, 5}, is symmetric.

    We define the adjacency relation on ZMod 8 by requiring (x + y).val to be 1, 3, or 5. Symmetry of the relation (x ~ y ↔ y ~ x) follows immediately from the commutativity of addition (add_comm) in ZMod 8.

    lines 1–12

    uses SimpleGraph.mk, add_comm

    /-- The Hankel-type adjacency relation on `ZMod 8`: `x ~ y` iff `(x + y).val ∈ {1, 3, 5}`. -/
    private abbrev exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel
        (x y : ZMod 8) : Prop :=
      (x + y).val = 1 ∨ (x + y).val = 3 ∨ (x + y).val = 5
    
    /-- The Hankel-type non-circulant graph on `ZMod 8` witnessing the statement. -/
    private abbrev exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph :
        SimpleGraph (ZMod 8) :=
      SimpleGraph.mk exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel
        ⟨fun x y h => by
          simpa only [exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel, add_comm]
            using h⟩
  2. The Hankel adjacency relation is irreflexive, defining a simple graph on ZMod 8.

    A loop would mean (x + x).val ∈ {1, 3, 5}. But x + x = 2x in ZMod 8, so (2x).val is always an even number in {0, 2, 4, 6} and cannot be 1, 3, or 5. Exhaustive evaluation over all 8 elements of ZMod 8 is carried out by decide to establish irreflexivity.

    lines 13–16

        ⟨fun x h =>
          (by decide : ∀ x : ZMod 8,
            ¬ exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel x x) x h⟩
    
  3. Adjacency in the Hankel-type graph is decidable.

    Unfolding the definition of the Hankel adjacency relation expresses it as a disjunction of equalities between natural numbers. Typeclass inference (infer_instance) synthesizes the Decidable instance from the decidability of equality on ℕ and boolean operations.

    lines 17–23

    /-- The Hankel-type graph has decidable adjacency. -/
    private instance exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph_inst :
        DecidableRel exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph.Adj :=
      fun x y =>
        (by unfold exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel; infer_instance :
          Decidable (exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel x y))
    
  4. There exists a simple graph on ZMod 8 with at least one edge that admits a sharp cyclic labeling and is not circulant.

    We supply the Hankel-type graph and its decidability instance as the witness. The graph contains at least one edge because 0 and 1 are adjacent (since (0 + 1).val = 1 ∈ {1, 3, 5}, checked by decide). Finally, the previously established theorems order_eight_hankel_admits_sharp_cyclic_labeling and order_eight_hankel_not_circulant show that this graph admits a sharp cyclic labeling and is not circulant, respectively, using Iff.rfl to identify the graph's adjacency relation with the Hankel condition.

    lines 24–33

    uses order_eight_hankel_admits_sharp_cyclic_labeling, order_eight_hankel_not_circulant, Iff.rfl

    /-- There exists a simple graph on 8 vertices with at least one edge that admits a sharp cyclic labeling and is not circulant. -/
    theorem exists_non_circulant_sharp_cyclic_graph_order_eight :
        ∃ (G : SimpleGraph (ZMod 8)) (_ : DecidableRel G.Adj),
          (∃ u v, G.Adj u v) ∧ admits_sharp_cyclic_labeling 8 G ∧ ¬ is_circulant_graph 8 G := ⟨exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph,
      exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph_inst,
      ⟨0, 1, by decide⟩,
      order_eight_hankel_admits_sharp_cyclic_labeling
        exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph (fun _ _ => Iff.rfl),
      order_eight_hankel_not_circulant
        exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph (fun _ _ => Iff.rfl)⟩
SimpleGraph.mk
Constructs a simple graph on a vertex type V from an adjacency relation, together with proofs that the relation is symmetric and irreflexive (loopless).
add_comm
Addition is commutative: a + b = b + a for all elements a, b.
order_eight_hankel_admits_sharp_cyclic_labeling
Any simple graph on ZMod 8 whose adjacency relation is (x + y).val ∈ {1, 3, 5} admits a sharp cyclic labeling.
order_eight_hankel_not_circulant
Any simple graph on ZMod 8 whose adjacency relation is (x + y).val ∈ {1, 3, 5} is not a circulant graph on ZMod 8.
Iff.rfl
Logical equivalence is reflexive: a ↔ a for every proposition a.

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

/-- The Hankel-type adjacency relation on `ZMod 8`: `x ~ y` iff `(x + y).val ∈ {1, 3, 5}`. -/private abbrev exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel    (x y : ZMod 8) : Prop :=  (x + y).val = 1 ∨ (x + y).val = 3 ∨ (x + y).val = 5/-- The Hankel-type non-circulant graph on `ZMod 8` witnessing the statement. -/private abbrev exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph :    SimpleGraph (ZMod 8) :=  SimpleGraph.mk exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel    ⟨fun x y h => by      simpa only [exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel, add_comm]        using h⟩    ⟨fun x h =>      (by decide : ∀ x : ZMod 8,        ¬ exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel x x) x h⟩/-- The Hankel-type graph has decidable adjacency. -/private instance exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph_inst :    DecidableRel exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph.Adj :=  fun x y =>    (by unfold exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel; infer_instance :      Decidable (exists_non_circulant_sharp_cyclic_graph_order_eight_hankelRel x y))/-- There exists a simple graph on 8 vertices with at least one edge that admits a sharp cyclic labeling and is not circulant. -/theorem exists_non_circulant_sharp_cyclic_graph_order_eight :    ∃ (G : SimpleGraph (ZMod 8)) (_ : DecidableRel G.Adj),      (∃ u v, G.Adj u v) ∧ admits_sharp_cyclic_labeling 8 G ∧ ¬ is_circulant_graph 8 G := ⟨exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph,  exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph_inst,  ⟨0, 1, by decide⟩,  order_eight_hankel_admits_sharp_cyclic_labeling    exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph (fun _ _ => Iff.rfl),  order_eight_hankel_not_circulant    exists_non_circulant_sharp_cyclic_graph_order_eight_hankelGraph (fun _ _ => Iff.rfl)⟩
See it in the graphDiscuss this resultChallenge it