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:
“But, where the road runs near the stream,
Oft through the trees they catch a glance
Of passing troops in the sun’s beam—
Pennon, and plume, and flashing lance!
Forth to the world those soldiers fare,
To life, to cities, and to war!”
—Matthew Arnold (1822–1888)