I'm new to Stackexchange, so please don't be too harsh on me. I took a course in graph minors, and I just started to dig a bit deeper into the material. I came across the following exercise about Treewidth that I found online. Now the exercise seemed quite interesting as it forces you to wrap your mind around the definition of Treewidth. The exercise is stated as follows, where $P_k$ is the set of graphs that do not contain a path of length $k$.
- Show that if $G \in P_k$ then $G$ has a tree-decomposition of width $\leq k^2$ and diameter $\leq 2k$.
- Show that if $G$ has a tree-decomposition of width $w-1$ and diameter $2d$, then $G$ has no path of length $(w+2)^{(d+1)}$.
Now I've been able to prove the first statement; I just added it for completion. And I think to have somewhat sketched a proof for the second part, but it turns out that my bound is tighter, namely $\leq (w+1)^{(d+1)} +1$. My idea is as follows:
Proof idea Take a tree-decomposition of width $w-1$, so every bag has at most $w$ many vertices. Now if there was a path $P$ using all the vertices in the first bag (the root of the tree) then it cannot use vertices from more than $w+1$ many bags that are direct children of the root. To see this take two vertices $v$ and $w$ from the root-bag (that are both part of the path), such that there is no other vertex in the root-bag that is on the path between $v$ and $w$. Then there cannot be two distinct vertices $v'$ and $w'$ from two distinct children bags that lie somewhere on $vPw$. Thus the path uses at most $(w+1)^j$ bags from layer $j$. It has at most $d+1$ layers as the diameter of the tree is $2d$. It could be "deeper" but then the layers would have less bags so i thought depth $d$ should give the largest path. Well and then there couldn't be paths of length $(w+1)^{(d+1)}+1$.
As you see it's even less than a sketch and really sloppy. I would appreciate any comment and maybe a rigorous proof or more rigorous explanations of why I might be right or wrong. Thanks everyone.