# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 4 Binary Graph Operations
### Substitution  
Let \(G_{1}\) and \(G_{2}\) be two vertex-disjoint graphs, and let \(v\in V(G_{1})\) be a vertex. The _substitution_ of \(v\) by \(G_{2}\) in \(G_{1}\), denoted by \(G_{1}[v/G_{2}]\), is defined as the graph with vertex set \((V(G_{1})\setminus\{v\})\cup V(G_{2})\) and edge set  
\[(E(G_{1})\setminus\{\{v,w\}\mid w\in N_{G_{1}}(v)\})\cup\{\{u,w\}\mid u\in V(G _{2}),w\in N_{G_{1}}(v)\}\cup E(G_{2}).\]  
The vertex set \(V(G_{2})\) is called a _module_ of the graph \(G_{1}[v/G_{2}]\), since all vertices of \(V(G_{2})\) are adjacent to the same vertices of \(V(G_{1}[v/G_{2}])\setminus V(G_{2})\) in \(G_{1}[v/G_{2}]\).  
Given this definition of substitution, the following theorem considers the tree-width (path-width) of \(G_{1}[v/G_{2}]\) in terms of the tree-width (path-width) of \(G_{1}\) and \(G_{2}\).  
Theorem 4.1: _For two vertex-disjoint graphs \(G_{1}\), \(G_{2}\) and vertex \(v\in V(G_{1})\), it holds that_  
\[\max(tw(G_{1}),tw(G_{2}))\leq tw(G_{1}[v/G_{2}])\leq\min(tw(G_{1})+|V(G_{2})|, tw(G_{2})+|V(G_{1})|)-1\]  
_and_  
\[\max(pw(G_{1}),pw(G_{2}))\leq pw(G_{1}[v/G_{2}])\leq\min(pw(G_{1})+|V(G_{2})|, pw(G_{2})+|V(G_{1})|)-1.\]  
Proof.: The lower bounds follow from Corollary 2, as \(G_{1}\) and \(G_{2}\) are subgraphs of \(G_{1}[v/G_{2}]\). For the upper bounds, this can be achieved in two ways:  
1. Replace \(v\) in every bag of a tree-decomposition (path-decomposition) of width \(\operatorname{tw}(G_{1})\) (\(\operatorname{pw}(G_{1})\)) for \(G_{1}\) with \(V(G_{2})\);
2. Add to every bag of a tree-decomposition (path-decomposition) of width \(\operatorname{tw}(G_{2})\) (\(\operatorname{pw}(G_{2})\)) for \(G_{2}\) the set \(V(G_{1})\setminus\{v\}\).  
As both alternatives result in a valid tree-decomposition (path-decomposition) for \(G_{1}[v/G_{2}]\), the upper bound follows.  
Note that the upper bounds described in the previous theorem are tight, as for two cliques \(K_{n},K_{m}\) and a vertex \(v\in V(K_{n})\), we have \(K_{n}[v/K_{m}]=K_{n+m-1}\) with  
\[\operatorname{tw}(K_{n+m-1})=n+m-2=\min(\operatorname{tw}(K_{n})+m, \operatorname{tw}(K_{m})+n)-1\quad\text{and}\] \[\operatorname{pw}(K_{n+m-1})=n+m-2=\min(\operatorname{pw}(K_{n})+m,\operatorname{pw}(K_{m})+n)-1.\]  
Besides this general upper bound for tree-width, the following proposition can provide an even stricter upper bound in specific situations.  
Proposition 9: _Let \(G_{1}\), \(G_{2}\) be two vertex-disjoint graphs, and let \(v\in V(G_{1})\) be a non-isolated vertex. Then, it holds that_  
\[tw(G_{1}[v/G_{2}])\leq\max(tw(G_{1})-1,tw(G_{2}))+|N_{G_{1}}(v)|.\]Proof.: Let \((\mathcal{X}_{1},T_{1})\) be a tree-decomposition for \(G_{1}\) of width \(\operatorname{tw}(G_{1})\), and let \((\mathcal{X}_{2},T_{2})\) be a tree-decomposition for \(G_{2}\) of width \(\operatorname{tw}(G_{2})\). Replace \(v\) with \(N_{G_{1}}(v)\) in every bag of \(\mathcal{X}_{1}\), and denote the modified set of bags by \(\mathcal{X}_{1}^{\prime}\). Then, \((\mathcal{X}_{1}^{\prime},T_{1})\) is a tree-decomposition for \(G_{1}\setminus\{v\}\) of width at most \(\operatorname{tw}(G_{1})-1+|N_{G_{1}}(v)|\). Subsequently, add \(N_{G_{1}}(v)\) to all bags of \(\mathcal{X}_{2}\), and denote the modified set of bags by \(\mathcal{X}_{2}^{\prime}\). Let \(v_{1}\in V(T_{1})\) be a vertex of \(T_{1}\) with \(N_{G_{1}}(v)\subseteq X_{v_{1}}\) for \(X_{v_{1}}\in\mathcal{X}_{1}^{\prime}\), and let \(v_{2}\) be any vertex of \(T_{2}\). Then, \((\mathcal{X},T)\) with \(\mathcal{X}=\mathcal{X}_{1}^{\prime}\cup\mathcal{X}_{2}^{\prime}\), \(V(T)=V(T_{1})\cup V(T_{2})\), and \(E(T)=E(T_{1})\cup E(T_{2})\cup\{v_{1},v_{2}\}\) is a tree-decomposition for \(G_{1}[v/G_{2}]\) of width at most \(\max(\operatorname{tw}(G_{1})-1,\operatorname{tw}(G_{2}))+|N_{G_{1}}(v)|\).