1
$\begingroup$

I have read the definition of treewidth/tree-decomposition both in Wikipedia and in here: https://medium.com/@karlrombauts/treewidth-how-all-graphs-are-trees-in-disguise-ec699b69e2fb

I'm finding something hard to understand why the treewidth of a tree is $1$. By the definition of tree-decomposition, I may select to have a single $X_1$ to contain all vertices. All requirements hold.

If we are referring to the $|X_1|$ it will be $n$ and then the tree width is $n-1$. If we are referring to the quantity of such sets, so we have only $X_1$, therefore the treewidth is $1-1=0$.

Likewise, this can be for any graph, not only trees. We can always decide $X_1$ will contain all vertices...

So I am not sure why it is claimed that the treewidth of a tree is exactly $1$? I think I'm missing out something in the understanding, and I'm looking for an explanation to this, and maybe one more example for a non-tree graph when the treewidth isn't trivially $1$.

Also, I read that $k$-treewidth do not contain $K_{k+2}$ as a minor. I'm not looking for a proof,but merely an intuition.

Edit: I understand now the width is the minimal maximal bag size. However, I still fail to see why any tree has width $1$. If the idea is $1$ bag for $1$ edge, wouldn't this be the case for any graph too? Why will it only work for a tree?

$\endgroup$
3
  • 1
    $\begingroup$ The width of a decomposition is the size of the largest bag. The width of a graph is the smallest possible width over all tree decompositions of the graph. Just because you choose a bad decomposition, doesn't mean that the width is large. It is always possible to make a tree decomposition of width 1 of any forest. $\endgroup$
    – Pål GD
    Jun 9, 2023 at 18:17
  • $\begingroup$ Thanks for the clarification. I still don't see what is the tree-decomposition of a tree/forest. Is it simply a bag per edge? If so, why can't we always construct a bag for an edge in a generic graph,and get width $1$? $\endgroup$ Jun 13, 2023 at 18:34
  • 1
    $\begingroup$ If you do that then the decomposition won't form a tree. There will be cycles in the decomposition. $\endgroup$ Jun 13, 2023 at 19:21

1 Answer 1

2
$\begingroup$

Yes, for a tree, the decomposition corresponds to one bag per edge. However, if you consider the graph $C_6$, the cycle on 6 vertices, you don't get a tree decomposition if you follow the same scheme.

What you would do for a cycle is essentially to pick an arbitrary vertex, $v_1$, remove it from the graph. Perform your trick with one bag per edge for the remaining graph (a $P_5$), and then put $v_1$ into every bag.

This naive trick works for every graph, i.e., find a smallest set $X$ such that $G-X$ is a forest, and then add $X$ to every bag. Warning: does not guarantee that the width is optimum, but does actually give you a valid tree decomposition, and perhaps some intuition. That also explains how adding one vertex can only increase the width of a graph with at most one.

(Ps, this set $X$ is called a feedback vertex set).

$\endgroup$
2
  • $\begingroup$ Thank you! I still don't see how having $K_{k+2}$ as a minor prevents the treewidth from being $k$. Is it perhaps a non-trivial result? Because your trick, as you said, doesn't guarantee we have no better way to decompose. $\endgroup$ Jun 19, 2023 at 15:47
  • $\begingroup$ There is a theorem starting that every treewidth-k graph has a k+1 sized separator. $\endgroup$
    – Pål GD
    Jun 19, 2023 at 17:38

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.