Path decomposition (graph theory)

A path decomposition of a finite graph is a sequence of vertex sets, called bags, $B_1,\dots ,B_t$, satisfying three conditions: every vertex appears, every edge has both endpoints together in a bag, and the bag indices containing each fixed vertex form an interval. Its width is ${\max }_i|B_i|-1$. Minimizing this width gives the pathwidth.

For the three-vertex path $1-2-3$, bags $\{1,2\},\{2,3\}$ have width one. Vertex two remains present while the decomposition passes from one edge to the next. The interval requirement forbids forgetting a vertex and later introducing it again, which is what permits dynamic programming to retain only the current bag's unresolved information.

For $K_n$, the intervals belonging to any pair of vertices intersect because their edge must be covered. Pairwise intersecting intervals have a common intersection, so some bag contains all $n$ vertices. Hence its pathwidth is $n-1$, showing that small width imposes a real structural restriction.