# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 3 Unary Graph Operations and Graph Transformations
### Edge Subdivision  
Let \(G\) be a graph, \(u\
ot\in V(G)\) be a newly introduced vertex, and \(\{v,w\}\in E(G)\) be an edge of \(G\). The _edge subdivision_ of \(\{v,w\}\) in \(G\), denoted by \(\operatorname{Subdiv}(G,v,w)\), consists of a vertex set \(V(G)\cup\{u\}\) and an edge set \((E(G)\setminus\{\{v,w\}\})\cup\{\{v,u\},\{u,w\}\}\). With this definition, the following theorem states the effect of an edge subdivision on the tree-width and path-width of a given graph. Theorem 3.1: _For a graph \(G\) and an edge \(\{v,w\}\in E(G)\), it holds that_  
\[\operatorname{tw}(\operatorname{Subdiv}(G,v,w)) =\operatorname{tw}(G)\quad\text{and}\] \[\operatorname{pw}(G) \leq\operatorname{pw}(\operatorname{Subdiv}(G,v,w)) \leq\operatorname{pw}(G)+1.\]  
Proof: \(G\) is isomorphic to \(\operatorname{Ident}(\operatorname{Subdiv}(G,v,w),u,w)\), such that the upper bounds of Theorem 3.1 yield  
\[\operatorname{tw}(G) =\operatorname{tw}(\operatorname{Ident}(\operatorname{Subdiv}( G,v,w),u,w))\leq\operatorname{tw}(\operatorname{Subdiv}(G,v,w))\quad\text{and}\] \[\operatorname{pw}(G) =\operatorname{pw}(\operatorname{Ident}(\operatorname{Subdiv}( G,v,w),u,w))\leq\operatorname{pw}(\operatorname{Subdiv}(G,v,w)),\]  
resulting in this theorem's lower bounds. For the upper bound of tree-width, let us distinguish the following two cases:  
**Case 1:**: \(\operatorname{tw}(G)=1\). In this case, \(G\) is a forest. Since an edge subdivision does not alter this fact, \(\operatorname{Subdiv}(G,v,w)\) is still a forest, and \(\operatorname{tw}(\operatorname{Subdiv}(G,v,w))=1\) must hold. **Case 2:**: \(\operatorname{tw}(G)>1\). In this case, the biggest bag of every tree-decomposition of \(G\) contains at least three vertices. Furthermore, by (tw-2), it follows that in every tree-decomposition of \(G\), there is at least one bag that contains \(v\) and \(w\). Let us denote this bag by \(X\). Adding a new bag \(X^{\prime}\) with vertices \(\{u,v,w\}\) and making it adjacent to \(X\) results in a tree-decomposition of \(\operatorname{Subdiv}(G,v,w)\) with unaltered size, such that \(\operatorname{tw}(\operatorname{Subdiv}(G,v,w))\leq\operatorname{tw}(G)\) follows. For the upper bound of path-width, we proceed as follows. By (pw-2), we know that in every path-decomposition of \(G\) there exists a bag containing \(v\) and \(w\). Adding \(u\) to this bag, we obtain a valid path-decomposition for \(\operatorname{Subdiv}(G,v,w)\). Consequently, \(\operatorname{pw}(\operatorname{Subdiv}(G,v,w))\leq\operatorname{pw}(G)+1\) follows. The upper bound for path-width given in the previous theorem is tight. The path-width of the caterpillar graph \(C\) in Figure 2c is equal to one. A _caterpillar_ graph is a tree for which the removal of all pendant vertices results in a chordless path. Conversely, the path-width of the graph obtained by subdividing edge \(\{c,f\}\) of \(C\), depicted as \(I(K_{1,3})\) in Figure 2b, is two. Please note that \(I(K_{1,3})\) is one of the two forbidden minors of the set of all graphs of path-width one (see [41] and Section 3.7). After subdividing all edges of a graph, the resulting graph must be bipartite. The resulting graph obtained after subdividing all edges of a graph \(G\) is called the _incidence graph_ of \(G\), denoted by \(I(G)\). The following corollary provides bounds for a graph's incidence graph and follows from Theorem 3.1. Corollary 3: _For a graph \(G\), it holds that_  
\[\operatorname{tw}(I(G)) =\operatorname{tw}(G)\quad\text{and}\] \[\operatorname{pw}(G) \leq\operatorname{pw}(I(G)) \leq\operatorname{pw}(G)+1.\]  
Proof: The result for tree-width follows directly from Theorem 3.1. By contracting all subdivided edges of \(I(G)\), we obtain \(G\). By Theorem 7, we know that edge contractions do not increase the resulting graph's path-width, such that \(\operatorname{pw}(G)\leq\operatorname{pw}(I(G))\) follows. Denote by \(\mathcal{X}\) a path-decomposition for \(G\) of width \(\operatorname{pw}(G)\), and let \(\{v,w\}\in E(G)\) be an edge of \(G\) and \(x_{\{v,w\}}\) be the node introduced to subdivide the edge.