# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 2 Preliminaries
### Tree-Width
Hence, \(\operatorname{tw}(G_{1})\leq\operatorname{tw}(G)\) holds, and we can repeat the previous argument for \(G_{1}\), i.e., remove a vertex and at most \(\operatorname{tw}(G)\) edges from \(G_{1}\). Repeating this argument for all vertices of \(G\) results in \(|E(G)|\leq\operatorname{tw}(G)|V(G)|\). After several repetitions of the previous argument, i.e., removing a vertex with at most \(\operatorname{tw}(G)\) incident edges from the remaining graph, there are at most \(\operatorname{tw}(G)\) vertices left in the remaining graph. This remaining graph can have a tree-width of at most \(\operatorname{tw}(G)-1\), such that by Lemma 1, it follows that in this graph, there is a vertex with degree at most \(\operatorname{tw}(G)-1\). Removing this vertex from the remaining graph, we remove at most \(\operatorname{tw}(G)-1\) edges. Repeating this argument for all of the \(\operatorname{tw}(G)\) remaining vertices in sequence yields  
\[|E(G)| \leq\operatorname{tw}(G)(|V(G)|-\operatorname{tw}(G))+\sum_{i=1}^ {\operatorname{tw}(G)}(\operatorname{tw}(G)-i)\] \[=\operatorname{tw}(G)(|V(G)|-\operatorname{tw}(G))+\operatorname{ tw}(G)\operatorname{tw}(G)-\sum_{i=1}^{\operatorname{tw}(G)}i\] \[=\operatorname{tw}(G)|V(G)|-\frac{1}{2}\operatorname{tw}(G)( \operatorname{tw}(G)+1).\]  
This completes the proof of the proposition. While the previous proposition provides an upper bound for the number of edges of a graph in terms of the number of its vertices and its tree-width, the following proposition by [PERSON] et al. [26] provides an upper bound for the tree-width of a graph in terms of the number of its edges and vertices. **Proposition 2**. : _Let \(G\) be a graph. Then, it holds that_  
\[\operatorname{tw}(G)\leq\frac{|E(G)|}{5.769}+\mathcal{O}(\log(|V(G)|)).\]  
Recall that a graph is said to be \(k\)-connected if and only if every pair of its vertices is connected by at least \(k\) vertex-disjoint paths [27]. Using Lemma 1, we obtain the following lower bound for the tree-width of \(k\)-connected graphs. **Lemma 2**: _Every \(k\)-connected graph has tree-width at least \(k\)._  
Let \(G\) be a \(k\)-connected graph. By definition, it holds that for all vertices \(u,v\in V(G)\), there exist \(k\) vertex-disjoint paths from \(u\) to \(v\) in \(G\). Consequently, \(\deg_{G}(u)\geq k\) and \(\deg_{G}(v)\geq k\) must be true. In other words, every vertex of \(G\) has degree at least \(k\). By the contraposition of Lemma 1, we immediately obtain \(\operatorname{tw}(G)\geq k\). To conclude the preliminary subsection on tree-width, we cite two lemmas by [PERSON] [PERSON] [28] that we make use of in later sections. **Lemma 3** (Clique containment): _Let \((\mathcal{X},T)\) be a tree-decomposition for a graph \(G\) and \(C\subseteq V(G)\) be a clique in \(G\). Then, there exists some \(u\in V(T)\) with \(C\subseteq X_{u}\)._  
**Lemma 4** (Complete bipartite subgraph containment): _Let \((\mathcal{X},T)\) be a tree-decomposition for a graph \(G\) and \(A,B\subseteq V(G)\) with \(A\cap B=\mathcal{O}\) and \(\{\{u,v\}\mid u\in A,v\in B\}\subseteq E(G)\). Then, there exists a vertex \(u\in V(T)\) with \(A\subseteq X_{u}\) or \(B\subseteq X_{u}\)._