A numerical measure of how close an undirected graph is to a tree, defined as the minimum over all tree decompositions of the maximum bag size minus one; small treewidth means the graph can be organized by small overlapping vertex sets arranged in a tree.

Principle

Organize a graph by a tree of overlapping vertex sets (bags) and use the largest bag as the cost metric; minimizing that maximum captures the smallest size of local interactions needed to reconstruct global structure.

Demonstration

A tree or any forest has treewidth 1 (bags contain two vertices at most); a simple path has treewidth 1, a cycle has treewidth 2, and the complete graph on n vertices has treewidth n−1; many dynamic-programming algorithms run in time exponential in the treewidth but polynomial in the graph size.

Misapplication

Treating degree, arboricity, or pathwidth interchangeably with treewidth and assuming small maximum degree implies small treewidth, or applying treewidth-based algorithms without producing a valid tree decomposition of bounded width.

Consequence

When a graph has bounded treewidth many problems that are hard in general (graph coloring, Hamiltonicity variants, constraint satisfaction) admit fixed-parameter or polynomial-time solutions parameterized by the treewidth; structural graph theory yields decomposition and minor theorems tied to treewidth.

Reversal

The inverse viewpoint is graphs with large treewidth (expanders, dense minors) which resist decomposition into small bags and exhibit global connectivity properties; high treewidth implies difficulty for local dynamic programming but may imply other combinatorial richness.

Boundary

Defined for undirected graphs via tree decompositions; extensions exist for directed graphs and hypergraphs but require different formulations; treewidth is invariant under taking minors but does not by itself measure sparsity in all senses and is distinct from related invariants like pathwidth or tree-depth.

Semantic Tension

Tension arises with pathwidth, tree-depth, and measures of sparsity: pathwidth restricts the decomposition shape, tree-depth measures height-like complexity, and density/arboricity measure edge distribution; each captures different structural constraints.

Synthesis

Treewidth condenses a graph's global complexity into the size of local overlapping pieces arranged as a tree: compute a tree decomposition minimizing the largest bag, and a small value signals that many global problems can be solved by local, tree-structured reasoning.