I am looking for ideas how to solve the problem from Diestel's textbook Graph Theory.
Chapter 12. Minors, Trees, and WQO.
Problem 16. Apply Theorem 12.3.9 to show that the $k \times k$ grid has tree-width at least $k$, and find a tree-decomposition of width exactly $k$.
Theorem 12.3.9. (Seymour & Thomas 1993). Let $k \geq 0$ be an integer. A graph has tree-width $\geq k$ if and only if it contains a bramble of order $> k$. (A bramble is a set of mutually touching connected vertex sets in $G$; its order is the minimum number of vertices in a set meeting each member of the bramble.)
The problem is the proof of the theorem 12.3.9 was given in the terms of bramble, which is a bit confusing, at present I don't really see the way to solve the problem by using this theorem.
If you familiar with the topic, please, help me out.
Addendum:
In Graphs & Algorithms: Advanced Topics on the slide 5.
The $n\times n$ – grid on $\left \{(i,k) | 1 \leq i, j \leq n\right \}$ has treewidth $\leq n$: Consider the path on
$X_{n(i-1)+j}=\left \{(i,k)|j\leq k\leq n\right \}\cup\left \{(i+1,k)|1\leq k\leq j\right \}, 1\leq i\leq n-1, 1\leq j\leq n$
How this is supposed to help me?
Best Answer
Here are a couple of big hints.
First, you need a bramble of order $k+1$. Let $G_k$ be the $k\times k$ grid, with vertices $\langle i,j\rangle$ for $1\le i,j\le k$. Thus, $G_{k-1}$ is the $(k-1)\times(k-1)$ grid in the upper lefthand corner of $G_k$. Start with the $(k-1)^2$ crosses in $G_{k-1}$; they form a bramble $\mathscr{B}$ of order $k-1$ for $G_{k-1}$. Of course these crosses don’t meet the bottom row and last column of $G_k$ at all. It’s possible to add just two sets to $\mathscr{B}$ to make a bramble of order $k+1$ for $G_k$. A good place to look for these sets is the part of $G_k$ that isn’t touched by $\mathscr{B}$ at all.
Then you need a tree decomposition of $G_k$ of width $k$. Uli Wagner’s slide 5 gives you one, though you still have to figure out the tree on which it’s based in order to prove that it is a tree decomposition. Note that he indexed the sets in the decomposition by consecutive integers; this is a big hint for the shape of the tree in question, and once you make the right guess, it isn’t hard to verify.