chain_tree_1
For any k, chain_tree_1 k is the graph formed by joining k copies of seed_tree_1 in a chain at vertex 9.
Statement
def chain_tree_1 (k : ℕ) : SimpleGraph (Fin k × Fin 16)- Defined in
- knowledgebase: OP-828
- Verified
- 02 Nov 2026
- Axioms
- none listed
- Built on 2
- seed_tree_1seed_tree_1 is the simple graph on Fin 16 whose edges are (1, 0), (1, 2), (1, 7), (1, 8), (0, 9), (2, 3), (2, 6), (3, 4), (4, 5), (9, 10),…
- chain_graphGiven 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…
- Used by 1
- chain_trees_extensive_mmi_gap_of_exact_claw_packingsFor any integer k ≥ 1, if max_claw_packing (chain_tree_1 k) = 5 * k / 2 in ℕ (using integer division) and max_claw_packing (chain_tree_2…
Read back from the Lean
chain_tree_1 is a definition taking a natural number $k$ and returning a simple graph on the vertex set $\text{Fin } k \times \text{Fin } 16$.
Two vertices $u = (i, x)$ and $v = (j, y)$ in $\text{Fin } k \times \text{Fin } 16$ are adjacent in chain_tree_1 k if and only if:
1. $i = j$ and $x$ is adjacent to $y$ in seed_tree_1 (i.e., within the same copy of the graph, $x$ and $y$ are connected according to seed_tree_1), or
2. $x = y = 9$ and $|i.val - j.val| = 1$ (i.e., between adjacent copies $i$ and $j$, the vertices at index 9 are connected).
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
/-- The k-unit chain tree T_k built from seed_tree_1 joined at marked vertex 9. -/ def chain_tree_1 (k : ℕ) : SimpleGraph (Fin k × Fin 16) := chain_graph seed_tree_1 ⟨9, by omega⟩ k