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:
“A lake is the landscape’s most beautiful and expressive feature. It is earth’s eye; looking into which the beholder measures the depth of his own nature. The fluviatile trees next the shore are the slender eyelashes which fringe it, and the wooded hills and cliffs around are its overhanging brows.”
—Henry David Thoreau (1817–1862)