Treewidth vs pathwidth

Same idea, but the scaffold is a path instead of a tree.

The definitions side by side

Pathwidth is exactly treewidth with one extra restriction: the underlying tree of the decomposition must be a path. So every pathwidth decomposition is a tree decomposition, which means pathwidth is always at least as large as treewidth: tw(G) ≤ pw(G).

Intuitively, pathwidth measures how well a graph can be swept in a single linear pass, while treewidth allows the sweep to branch. Branching is strictly more powerful, so a graph can have small treewidth and large pathwidth — but never the reverse.

When the gap is large

A complete binary tree of height h has treewidth 1 (it is a tree) but pathwidth roughly h. The branching that a path decomposition cannot exploit is precisely what the tree decomposition uses for free. This gap is the cleanest demonstration that the shape of the scaffold matters.