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)))