some bag of $T$ does not contain $k+1$ vertices, then as $T$ is connected, there exist adjacent bags $X$ and $Y$ such that $|X|=k+1$ and $|Y|<k+1$. Then $X-Y$ is non-empty; take some vertex of $X-Y$ and add it to $Y$. This increases $|Y|$, so repeat this process until all bags have size $k+1$.

Now, consider an edge $XY$. Since $|X|=|Y|$, it follows $|X-Y|=|Y-X|$. If $|X-Y| > 1$, then let $v \in X-Y$ and $u \in Y-X$. Subdivide the edge $XY$ of $T$ and call the new bag $Z$. Let $Z = X - \{v\} + \{u\}$. Now $|X-Z| = 1$ and $|Y-Z|=|Y-X|-1$, so repeat this process until $|X-Y|=|Y-X| \leq 1$ for each pair of adjacent bags. Finally, if $XY$ is an edge and $|X-Y|=0$, then contract the edge $XY$, and let the bag at the contracted node be $X$. Repeat this process so that if $X$ and $Y$ are a pair of adjacent bags, then $|X-Y|=|Y-X|=1$. All of these operations preserve tree decomposition properties and width. Hence this modified $T$ is our desired normalised tree decomposition.

A *$k$-colouring* of a graph $G$ is a function that assigns one of $k$ colours to each vertex of $G$ such that no pair 