Treewidth

Summary

Treewidth is a number that measures how close a graph is to a tree. It is defined through tree decompositions, which arrange overlapping sets of vertices along a tree. Forests have treewidth at most $1$, and the complete graph $K_n$ has treewidth $n - 1$. Treewidth is central in the theory of graph minors. Many problems that are hard in general can be solved efficiently on graphs of bounded treewidth.