According to some slides I found on google, the treewidth of any $k \times k$ square grid graph $G$ is $tw(G) = k$. I just started researching about treewidth and tree decomposition, and for the most part it makes sense. However, I am particularly interested in the $k \times k$ square grid graph case, but have been struggling on how it is possible to make a tree decomposition of such a graph with that low of a width.
One of the problems I run into when trying to draw out decomposition trees of small square grids with groups of at most $k+1$ (to ensure a decomposition tree where the width is $k$) is that since the graph is "cyclic", one of the corner nodes shows up in two opposite ends of the tree, but not in any nodes on the path between the two. This clearly violates the coherence property of decomposition trees, which according to Wikipedia (which gives a more precise definition than most) is:
If $X_{i}$, $X_{j}$, and $X_{k}$ are nodes (in the decomposition tree), and $X_{k}$ is on the path from $X_{i}$ to $X_{j}$, then $X_{i}\cap X_{j}\subseteq X_{k}$.
For the case of the $3 \times 3$ graph, the only valid (or at least what I believe to be valid) decomposition tree I can think of contains 2 nodes: $\{\{1, 2, 3, 4, 6, 7, 8, 9\}, \{2, 4, 5, 6, 8\}\}$ where the nodes are labeled by row starting from the top left corner:
$1\space2\space3$
$4\space5\space6$
$7\space8\space9$
I did this by taking the perimeter vertices for the first tree node, and the inner vertex ($5$) along with its adjacent vertices to ensure all edges and vertices are included.
Ultimately, my question is, how can the treewidth of a square $k \times k$ square grid graph actually be equal to $k$? And if this is correct, could you present/explain a simple example of a decomposition tree that demonstrates this property?
