# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 2 Preliminaries
### Tree-Width  
One of the most famous tree-structured graph classes is the class of graphs of bounded tree-width. The first notion equivalent to tree-width, the dimension of a graph, was introduced by [PERSON] and [PERSON] [21] in 1973. The following definition of tree-width was given by [PERSON] and [PERSON] [1] in 1986. **Definition 1** (Tree-width). : _A tree-decomposition of a graph \(G\) is a pair \((\mathcal{X},T)\), where \(T\) is a tree and \(\mathcal{X}=\{X_{u}\subseteq V(G)\mid u\in V(T)\}\) is a family of subsets of \(V(G)\), called bags, such that the following three conditions hold:_  
**(tw-1)**: \(\bigcup_{u\in V(T)}X_{u}=V(G)\)_._
**(tw-2)**: _For every edge_ \(\{v_{1},v_{2}\}\in E(G)\)_, there is a node_ \(u\in V(T)\) _with_ \(v_{1},v_{2}\in X_{u}\)_._
**(tw-3)**: _For every vertex_ \(v\in V(G)\)_, the subgraph of_ \(T\) _induced by the nodes_ \(u\in V(T)\) _with_ \(v\in X_{u}\) _is connected._  
_The width of a tree-decomposition \((\mathcal{X}=\{X_{u}\mid u\in V(T)\},T)\) is defined as_  
\[\max_{u\in V(T)}|X_{u}|-1.\]  
_Finally, the tree-width of a graph \(G\), denoted by \(\text{tw}(G)\), is the smallest integer \(k\), such that there is a tree-decomposition \((\mathcal{X},T)\) for \(G\) of width \(k\)._  
Please note that (tw-1) has no influence on the width of a tree-decomposition. It merely ensures that isolated vertices are covered by a tree-decomposition, which is useful for the design of algorithms along tree-decompositions. Obviously, the tree-width of every graph \(G\) is bounded by \(|V(G)|-1\), as one can always place all its vertices in a single bag. Conversely, determining whether the tree-width of a given graph is at most a given integer \(w\) is NP-complete, even for bipartite graphs and complements of bipartite graphs [10]. **Example 1** (Tree-decomposition). : _Figure 1 depicts a graph together with a corresponding tree-decomposition of width \(1\)._  
In addition to the previous definition of tree-width, tree-width can also be defined by bramble numbers [22] (also known as the size of screens [23]) or partial \(k\)-trees [24]. We refer the reader to the work by [PERSON] [7] for an overview of equivalent definitions. Throughout the course of our work, we make use of the following lemma by [PERSON] [25] several times. Figure 1: (**a**) A graph and (**b**) a corresponding tree-decomposition. **Lemma 1**. : _Every graph of tree-width at most \(k\) has a vertex of degree at most \(k\)._  
Proof. : Let \(G\) be a graph with \(\operatorname{tw}(G)=k\) and \((\mathcal{X},T)\) be a tree-decomposition of width \(k\) for \(G\), such that \(|V(T)|\) is as small as possible. Let \(\ell\) be a leaf of \(T\) and denote its parent in \(T\) as \(v\). Since \(|V(T)|\) is as small as possible, there must exist a vertex \(u\in X_{\ell}\) with \(u\
otin X_{v}\). Otherwise, \(X_{\ell}\subset X_{v}\) holds, and we can delete \(X_{\ell}\), contradicting the minimality of \(V(T)\). Thus, due to (tw-2) and (tw-3), all neighbors of \(u\) must be in \(X_{\ell}\) and, as \(X_{\ell}\) contains at most \(k+1\) vertices, it follows that \(u\) has degree at most \(k\). The following proposition was stated by [PERSON] [7], who credited it to [PERSON] [24]. As [PERSON]'s proof makes use of \(k\)-trees, we provide, for the sake of self-containment, a proof that relies only on Lemma 1 and tree-width. **Proposition 1**. : _Let \(G\) be a graph. Then, it holds that_  
\[|E(G)|\leq\operatorname{tw}(G)|V(G)|-\frac{1}{2}\operatorname{tw}(G)( \operatorname{tw}(G)+1).\]  
Proof. : By Lemma 1, we know that there exists at least one vertex \(v\) in \(G\) of degree at most \(\operatorname{tw}(G)\), such that \(v\) has at most \(\operatorname{tw}(G)\) incident edges in \(G\). Let us denote the graph we obtain by removing \(v\) from \(G\) as \(G_{1}\). Then, we know that from \(G\) to \(G_{1}\), we removed at most \(\operatorname{tw}(G)\) edges from \(G\). It is easy to see that removing \(v\) and all its incident edges from \(G\) can reduce the tree-width of \(G\) but not increase it.