On the page 6 of the paper [Simulating quantum circuits by contracting tensor network](https://arxiv.org/abs/quant-ph/0511069) author wrote about the equivalence of *treewidth* of a Graph and its *induced width* where the *treewidth* is defined through the tree decompositions and the *induced width* - as the maximum degree of a graph vertex at the time of its elimination. Unfortunately, the referenced survey (5) doesn't provide enough details for me to understand it. What is a good proof of this fact?



What is the proof of the graph treewidth and the induced graph width equivalence?
If a graph $G$ has treewidth $\leq k$, then it is a subgraph of a [$k$-tree](https://en.wikipedia.org/wiki/K-tree).
By taking a [perfect elimination sequence](https://en.wikipedia.org/wiki/Chordal_graph#Perfect_elimination_and_efficient_recognition), the graph $G$ turns our to have induced width $\leq k$.


Conversely, suppose a graph $G$ has induced width $\leq k$. Let $\pi$ be a elimination ordering of $G$. Let $H$ be a graph with the same vertices of $G$ and two vertices of $H$ are connected iff they are once connected in the elimination ordering process. The graph $H$ is a $k$-tree and contains $G$ as a subgraph (because all the edges of $G$ are present in the beginning of the elimination ordering process). So $G$ is contained in a $k$-tree and thus has treewidth $\leq k$.


