# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 3 Unary Graph Operations and Graph Transformations
### Vertex Identification  
For a graph \(G\) and two different vertices \(v,w\in V(G)\), the _identification_ of \(v\) and \(w\) in \(G\), denoted by \(\text{Ident}(G,v,w)\), consists of a vertex set \((V(G)\setminus\{v,w\})\cup\{u\}\) and an edge set  
\[E(G)\setminus\{\{x,y\}\mid x\in V(G),y\in\{v,w\}\}\] \[\cup\{\{x,u\}\mid x\in(N_{G}(v)\cup N_{G}(w))\setminus\{v,w\}\}.\]  
Given this definition of vertex identification, the following result summarizes the graph operation's effect on the tree-width and path-width of the involved graph.  
Theorem 3.3: _For a graph \(G\) and two different vertices \(v,w\in V(G)\), it holds that_  
\[tw(G)-1 \leq tw(\text{Ident}(G,v,w))\leq tw(G)+1\quad\text{and}\] \[pw(G)-1 \leq pw(\text{Ident}(G,v,w))\leq pw(G)+1.\]Proof.: For the upper bounds, let \((\mathcal{X},T)\) be a tree-decomposition (\(\mathcal{X}\) be a path-decomposition) for \(G\) of width \(\operatorname{tw}(G)\) (\(\operatorname{pw}(G)\)). To obtain a tree-decomposition (path-decomposition) for \(\operatorname{Ident}(G,v,w)\), we proceed as follows. In the first step, replace all occurrences of \(v\) and \(w\) in all bags of \(\mathcal{X}\) with \(u\) and denote the result by \(\mathcal{X}^{\prime}\). Since \(\{v,w\}\) is not necessarily an edge of \(G\), \(\mathcal{X}^{\prime}\) could violate (tw-3) ((pw-3)), i.e., the bags of \(\mathcal{X}^{\prime}\) containing \(u\) might not be connected. In this case, we add \(u\) to all bags between the disconnected components. With this, \((\mathcal{X}^{\prime},T)\) is a valid tree-decomposition (\(\mathcal{X}^{\prime}\) is a valid path-decomposition) for \(\operatorname{Ident}(G,v,w)\). To obtain \(\mathcal{X}^{\prime}\) from \(\mathcal{X}\), we increase the width by at most one, such that \(\operatorname{tw}(\operatorname{Ident}(G,v,w))\leq\operatorname{tw}(G)+1\) (\(\operatorname{pw}(\operatorname{Ident}(G,v,w))\leq\operatorname{pw}(G)+1\)) follows.  
For the lower bounds, we proceed as follows. First, rename vertex \(u\) of \(\operatorname{Ident}(G,v,w)\) to \(v\) and denote the resulting graph by \(G^{\prime}\). Next, add a new vertex \(w\) with neighborhood \(N_{G}(w)\) to \(G^{\prime}\). By Theorem 3, it follows that \(\operatorname{tw}(G^{\prime}+_{N_{G}(w)}w)\leq\operatorname{tw}(G^{\prime})+1\) and \(\operatorname{pw}(G^{\prime}+_{N_{G}(w)}w)\leq\operatorname{pw}(G^{\prime})+1\) are true. Since \(G\) is a subgraph of \(G^{\prime}+_{N_{G}(w)}w\), with Corollary 2, we obtain that  
\[\operatorname{tw}(G) \leq\operatorname{tw}(G^{\prime}+_{N_{G}(w)}w)\leq\operatorname{ tw}(\operatorname{Ident}(G,v,w))+1\quad\text{and}\] \[\operatorname{pw}(G) \leq\operatorname{pw}(G^{\prime}+_{N_{G}(w)}w)\leq\operatorname{ pw}(\operatorname{Ident}(G,v,w))+1\]  
hold, which yields the lower bounds \(\operatorname{tw}(G)-1\leq\operatorname{tw}(\operatorname{Ident}(G,v,w))\) and \(\operatorname{pw}(G)-1\leq\operatorname{pw}(\operatorname{Ident}(G,v,w))\).  
Note that the upper bounds specified in the previous theorem are tight, since a vertex identification on the end vertices of a path results in a cycle with increased tree-width and path-width.