On the page 6 of the paper Simulating quantum circuits by contracting tensor network 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?
1 Answer
If a graph $G$ has treewidth $\leq k$, then it is a subgraph of a $k$-tree. By taking a perfect elimination sequence, 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$.