where $A$ is a clique on $n$ vertices, $B$ is an independent set on $kn$ vertices, and $A \cap B = \emptyset$, such that each vertex of $A$ is adjacent to exactly $k(n-1)$ vertices of $B$ and each vertex of $B$ is adjacent to exactly $n-1$ vertices of $A$. (Note it always possible to add edges in this fashion; pair up each vertex in $A$ with $k$ vertices in $B$ such that all pairs are disjoint, and then add all edges from $A$ to $B$ except those between paired vertices.)

![The graph $\psi_{4,2}$.](psi_graph)

Treewidth and Basics
====================

Let $G$ be a graph. A *tree decomposition* of $G$ is a pair $(T, (B_x \subseteq V(G))_{x \in V(T)})$ consisting of

-   a tree $T$,

-   a collection of *bags* $B_x$ containing vertices of $G$, indexed by the nodes of $T$.

The following conditions must also hold:

-   For all $v \in V(G)$, the set $\{ x \in V(T) : v \in B_x\}$ induces a non-empty subtree of $T$.

-   For all $vw \in E(G)$, there is some bag $B_x$ containing both $v$ and $w$.

The *width* of a tree decomposition is defined as the size of the largest bag minus 1. The 