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:
“One wonders that the tithing-men and fathers of the town are not out to see what the trees mean by their high colors and exuberance of spirits, fearing that some mischief is brewing. I do not see what the Puritans did at this season, when the maples blaze out in scarlet. They certainly could not have worshiped in groves then. Perhaps that is what they built meeting-houses and fenced them round with horse-sheds for.”
—Henry David Thoreau (1817–1862)