Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
