Treewidth of k x k square grid graphs
The treewidth (and pathwidth) of the $k\times k$ grid is exactly $k$. (And, more generally, the treewidth and pathwidth of the $k\times\ell$ grid is exactly $\min\,\{k,\ell\}$). For the example grid

$$\begin{matrix}1&amp;-&amp;2&amp;-&amp;3\\|&amp;&amp;|&amp;&amp;|\\4&amp;-&amp;5&amp;-&amp;6\\|&amp;&amp;|&amp;&amp;|\\7&amp;-&amp;8&amp;-&amp;9\end{matrix}$$

the bags of the tree decomposition are $\{1,2,3,4\}, \{2,3,4,5\}, \{3,4,5,6\}, ..., \{6,7,8,9\}$.

Note that the bag $\{1,2,3,4\}$ already contains all edges adjacent to&nbsp;$1$, so we don't need to include that vertex ever again. Similarly, $\{2,3,4,5\}$ contains all of the edges adjacent to&nbsp;$2$ that weren't already in the first bag.