# If G has no simple path on x vertices ,then the treewidth of G is upper bounded by x

Statement: If G has no simple path on x vertices ,then the treewidth of G is upper bounded by x.

Hint: Begin by computing a DFS tree, and prove an upper bound on its height.

I am supposed to prove the above statement. I tried but without success. I would be happy If you can help me to solve, thanks in advance.

Suppose for simplicity that $$G$$ is connected. Otherwise the following argument works for each connected component of $$G$$.
Pick an arbitrary vertex $$v$$ of $$G$$ and let $$T$$ be any DFS tree of $$G$$ rooted at $$v$$. If the height $$h$$ of $$T$$ was larger than $$x$$ then there would be a simple path from $$v$$ to a leaf of $$T$$ of length at least $$x+1$$, which is a contradiction. Therefore $$h \le x$$.
Define a tree decomposition by replacing each vertex $$v$$ of $$T$$ with a bag containing all the (not necessarily proper) ancestors of $$v$$ in $$T$$. Notice that the endpoints of each edge $$(u,v)$$ in $$G$$ are in an ancestor-descendant relation in $$T$$, therefore either $$u$$'s bag contains $$v$$ or $$v$$'s bag contains $$u$$. The other properties of a tree decomposition are trivial to check.
The size of the largest bag is then at most $$x+1$$, and hence the treewidth of $$G$$ is at most $$x$$.