Treewidth of Trees
A connected graph with at least two vertices has treewidth 1 if and only if it is a tree. This can be shown in two steps, first that a tree has treewidth 1, second, that a connected graph with treewidth 1 is a tree.
To show the former, use induction on the number of vertices in the tree to show that it has a tree decomposition with no bag with size larger than two. The base case is a tree with two vertices, in which case the tree decomposition with one single node is sufficient. The inductive case is a tree with vertices, where is any integer greater than . If we remove a leaf from the graph, we get a tree of size . From the induction hypothesis we can create a tree decomposition of width 1 of this graph. Let be the unique neighbour of in and some node in such that is in . Let be added a node with as its only neighbour and let be with the addition that . Now is a tree decomposition of with width 1.
Now it remains to show that a connected graph with treewidth 1 is a tree. The contrapositive statement is that a graph with a cycle does not have treewidth 1. A graph with a cycle has the 3-clique as a minor, which from the statement in the previous section has treewidth 2. Since the partial 2-trees are closed under minors, the graph therefore has treewidth 2 or greater.
Read more about this topic: Tree Decomposition
Famous quotes containing the word trees:
“I do not know but it is too much to read one newspaper a week. I have tried it recently, and for so long it seems to me that I have not dwelt in my native region. The sun, the clouds, the snow, the trees say not so much to me. You cannot serve two masters.”
—Henry David Thoreau (1817–1862)