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?

• 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. Commented Jun 9, 2023 at 18:17
• 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$? Commented Jun 13, 2023 at 18:34
• If you do that then the decomposition won't form a tree. There will be cycles in the decomposition. Commented Jun 13, 2023 at 19:21

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).
• 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. Commented Jun 19, 2023 at 15:47