treewidth ${\textsf{\textup{tw}}}(G)$ is the minimum width over all tree decompositions of $G$. Often, for the sake of simplicity, we will refer to a tree decomposition simply as $T$, leaving the set of bags implied whenever this is unambiguous. For similar reasons, often we say that bags $X$ and $Y$ are adjacent (or we refer to an edge $XY$), instead of the more accurate statement that the nodes of $T$ indexing $X$ and $Y$ are adjacent.

Treewidth was defined by @Halin76 (in an equivalent form which Halin called $S$-functions) and independently by @RS-GraphMinorsII-JAlg86. Intuitively, a graph with low treewidth is simple and treelike — note that a tree itself has treewidth 1. (In fact, ensuring this fact is the reason that 1 was subtracted in the definition of width.) On the other hand, a complete graph $K_{n}$ has treewidth $n-1$.

Say a tree decomposition is *normalised* if each bag has the same size, and if $|X-Y|=|Y-X|=1$ whenever $XY$ is an edge.

\[lemma:normal\] If $G$ has a tree decomposition of width $k$, then $G$ has a normalised tree decomposition of width $k$.

Let $T$ be the tree decomposition of $G$ with width $k$. Thus $T$ contains a bag of size $k+1$. If 