Treewidth: How all graphs are trees in disguise!
In order to better understand graphs, we commonly describe them using several statistics and properties such as the number of edges and vertices, maximum clique size, colourability, planarity etc. One such property which is particularly useful is treewidth. Informally, treewidth is an integer which measures how close an undirected graph is from being a tree.
Treewidth is an interesting property because many important graph problems that are NP-complete are solvable in polynomial time when the input graph is bounded by a constant treewidth. Some examples include:
Also, many graphs that we find in practice have a small treewidth, which means that bounding graphs by treewidth is definitely a viable angle of attack for these difficult problems.
k-trees
One way to think about treewidth is by generalising the notion of a tree. For a regular tree, the minimal graph, which is not just a single vertex, is an edge. Given a tree with n vertices, a new tree with n + 1 vertices can be constructed by adding a new vertex to the tree, which is connected to any of the other existing vertices