the edge-maximal graphs for a fixed tree-width.

\[lemma:ktree\] $$\begin{aligned}
{\textsf{\textup{tw}}}(G) &= \min\{ k: G \text{ is a spanning subgraph of a $k$-tree }\}. \\
 &= \min\{ k: G \text{ is a spanning subgraph of a chordal graph with no $(k+2)$-clique }\}.\end{aligned}$$

For simplicity, let $a(G) = \min\{ k: G$ is a spanning subgraph of a $k$-tree$\}$ and $b(G) = \min\{ k: G$ is a spanning subgraph of a chordal graph with no $(k+2)$-clique$\}$.

First, show $b(G) \leq a(G)$. @FG65 showed that a graph $H$ is chordal if and only if it has a *perfect elimination ordering*; that is, an ordering of the vertex set such that for each $v \in V(H)$, $v$ and all vertices adjacent to $v$ which are after $v$ in the ordering form a clique. If $H$ be an $a(G)$-tree such that $G$ is a spanning subgraph of $H$, then there is a simple perfect elimination ordering for $H$. (Repeatedly delete the $a(G)$-simplicial vertices to obtain $K_{a(G)+1}$, and consider the order of deletion.) So $H$ is chordal. It is clear that each $v$ has only $a(G)$ neighbours after it in this ordering, so $H$ has no $(a(G)+2)$-clique. (For any clique, consider the first vertex of the clique 