AFTD Auto-Formalizing Theoretical Domains

chain_graph

def

Given a graph G on Fin m and a marked vertex v0, chain_graph G v0 k is the graph on Fin k × Fin m formed by k copies of G connected linearly by edges between consecutive copies at v0.

Statement

def chain_graph {m : ℕ} (G : SimpleGraph (Fin m)) (v0 : Fin m) (k : ℕ) :
    SimpleGraph (Fin k × Fin m)
Defined in
knowledgebase: OP-828
Verified
02 Nov 2026
Axioms
none listed
Used by 2
  • chain_tree_1For any k, chain_tree_1 k is the graph formed by joining k copies of seed_tree_1 in a chain at vertex 9.
  • chain_tree_2For any k, chain_tree_2 k is the graph formed by joining k copies of seed_tree_2 in a chain at vertex 1.

Read back from the Lean

Given an implicit natural number m, a simple graph G on Fin m, a vertex v0 : Fin m, and an explicit natural number k, chain_graph G v0 k is the simple graph on the vertex type Fin k × Fin m constructed via SimpleGraph.fromRel from the relation relating two vertices u and v if and only if: 1. u.1 = v.1 and u.2 is adjacent to v.2 in G; or 2. u.2 = v0 and v.2 = v0, and either u.1.val + 1 = v.1.val or v.1.val + 1 = u.1.val.

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

Lean source view module on GitHub

/-- Chain of k copies of a marked finite simple graph connected at the marked vertex. -/
def chain_graph {m : ℕ} (G : SimpleGraph (Fin m)) (v0 : Fin m) (k : ℕ) :
    SimpleGraph (Fin k × Fin m) := SimpleGraph.fromRel (fun u v =>
    (u.1 = v.1 ∧ G.Adj u.2 v.2) ∨
    (u.2 = v0 ∧ v.2 = v0 ∧ (u.1.val + 1 = v.1.val ∨ v.1.val + 1 = u.1.val)))
See it in the graphDiscuss this resultChallenge it