What is treewidth?

The number that says how far a graph is from being a tree.

The one-sentence version

Treewidth is a number, tw(G), that measures how close a graph G is to being a tree. A tree has treewidth 1. A complete graph on n vertices has treewidth n−1. Everything else falls in between, and the position it lands at predicts how hard the graph is to compute over.

The intuition: many hard graph problems become easy on trees, because a tree can be processed leaf-to-root with dynamic programming, carrying only a small amount of state across each edge. Treewidth asks how well an arbitrary graph can be reshaped into a tree without ever bundling too many vertices into a single node.

Why a single number can mean so much

A graph of low treewidth is a tree wearing a small amount of disguise. You can peel the disguise off — find a tree-shaped scaffold whose nodes are small bags of vertices — and then run the same linear-time sweep that works on real trees. The width is the size of the largest bag minus one, so it is literally the amount of state you must carry across the worst cut.

This is why treewidth shows up everywhere from constraint satisfaction to probabilistic inference to quantum-circuit simulation: in each case the running time is exponential in the width and only linear in the size of the graph. The width is the exponent; everything else is a constant factor.

In the thesis

Shadow & Mirror takes treewidth as the universal meter — the same invariant that prices a tensor-network contraction also prices a constraint network and a knowledge graph. The claim is not that these are analogies but that they are the same measurement applied to different substrates.