# How does treewidth behave under graph minor operations?

It is a well-known fact that for any minor H of a graph G (commonly written as $$H \leq_m G$$), the treewidth of H is smaller than or equal to that of G.

Minors of a graph are created through the operations of (1) vertex deletion, (2) edge deletion and (3) edge contraction. I am curious as to whether one can bound the decrease in treewidth when applying any single operation from (1)-(3). Of particular interest for me is the question whether said decrease can always be bounded by some constant.

## 1 Answer

The decrease in tree width of any of the three operations will be 0 or 1. The proof is simple (I will take the case of the vertex deletion).

Let $$G$$ be the original graph and $$G' = G - v$$ be the graph obtained by deleting $$v$$.

Let $$T'$$ be an optimal tree decomposition of $$G'$$, with $$\text{tw}(G') = w'$$.

Now, construct $$T$$ from $$T'$$ by adding $$v$$ to every bag of $$T'$$. Clearly, $$T$$ is a tree decomposition for $$G$$ with width $$\text{tw}(G) \leq \text{tw}(T) = 1 + \text{tw}(G') = 1 + w'$$.

• Indeed, it seems trivial now. Thank you. – SmeltQuake Feb 17 at 15:06