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.


1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.