# The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
## 4 Binary Graph Operations
### 1-Sum  
Let \(G_{1}\) and \(G_{2}\) be two vertex-disjoint graphs, and let \(v\in V(G_{1})\) and \(w\in V(G_{2})\) be two vertices. The 1-_sum_ of \(G_{1}\) and \(G_{2}\), denoted by \(G_{1}\oplus_{v,w}G_{2}\), consists of the disjoint union of \(G_{1}\) and \(G_{2}\), with vertices \(v\) and \(w\) identified. More specifically, graph \(G_{1}\oplus_{v,w}G_{2}\) has vertex set \((V(G_{1})\cup V(G_{2})\cup\{z\})\setminus\{v,w\}\) for a newly introduced vertex \(z\) and edge set  
\[E(G_{1})\cup E(G_{2}) \setminus\{\{v,v_{1}\}\mid v_{1}\in N_{G_{1}}(v)\}\] \[\setminus\{\{w,w_{1}\}\mid w_{1}\in N_{G_{2}}(w)\}\] \[\cup\{\{z,z_{1}\}\mid z_{1}\in(N_{G_{1}}(v)\cup N_{G_{2}}(w))\}.\]  
With the 1-sum of two graphs \(G_{1}\) and \(G_{2}\) formally defined, the following theorem considers the tree-width and path-width of \(G_{1}\oplus_{v,w}G_{2}\). **Theorem 25**: _Let \(G_{1}\) and \(G_{2}\) be two vertex-disjoint graphs, and let \(v\in V(G_{1})\) and \(w\in V(G_{2})\) be two vertices. Then, it holds that_  
\[ \begin{split} tw(G_{1}\oplus_{v,w}G_{2})&=\max(tw(G_ {1}),tw(G_{2}))\quad\text{and}\\ \max(pw(G_{1}),pw(G_{2}))&\leq pw(G_{1}\oplus_{v,w}G _{2})&\leq\max(pw(G_{1}),pw(G_{2}))+1.\end{split} \]  
Proof. : The lower bounds follow from Corollary 2, as \(G_{1}\) and \(G_{2}\) are subgraphs of \(G_{1}\oplus_{v,w}G_{2}\). 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})\). To define a tree-decomposition \((\mathcal{X},T)\) for \(G_{1}\oplus_{v,w}G_{2}\), we replace every occurrence of \(v\) in \(\mathcal{X}_{1}\) and every occurrence of \(w\) in \(\mathcal{X}_{2}\) with \(z\). Then, we choose a vertex \(u_{1}\) in \(V(T_{1})\) such that \(z\) belongs to \(X_{u_{1}}\in\mathcal{X}_{1}\), and a vertex \(u_{2}\) in \(V(T_{2})\) such that \(z\) belongs to \(X_{u_{2}}\in\mathcal{X}_{2}\). We define \(T\) as the disjoint union of \(T_{1}\) and \(T_{2}\) with the additional edge \(\{u_{1},u_{2}\}\) and \(\mathcal{X}\) as the union of \(\mathcal{X}_{1}\) and \(\mathcal{X}_{2}\). This results in a tree-decomposition \((\mathcal{X},T)\) for \(G_{1}\oplus_{v,w}G_{2}\) of width \(\max(\operatorname{tw}(G_{1}),\operatorname{tw}(G_{2}))\). In order to define a path-decomposition for \(G_{1}\oplus_{v,w}G_{2}\), let \(\mathcal{X}_{1}\) be a path-decomposition for \(G_{1}\) of width \(\operatorname{pw}(G_{1})\), and let \(\mathcal{X}_{2}\) be a path-decomposition for \(G_{2}\) of width \(\operatorname{pw}(G_{2})\). Then, we can either proceed as with tree-width, replacing \(v\) in all bags of \(\mathcal{X}_{1}\) and \(w\) in all bags of \(\mathcal{X}_{2}\) with \(z\), and concatenate both sequences of bags into a new path \(\mathcal{X}\), resulting in a path-decomposition for \(G_{1}\oplus_{v,w}G_{2}\) of width \(\max(\operatorname{pw}(G_{1}),\operatorname{pw}(G_{2}))\), or, if the resulting concatenation violates (pw-3), add \(z\) to all remaining bags of \(\mathcal{X}\), resulting in a path-decomposition of width at most \(\max(\operatorname{pw}(G_{1}),\operatorname{pw}(G_{2}))+1\). If \(v\in V(G_{1})\) and \(w\in V(G_{2})\) have degree at least one in \(G_{1}\) and \(G_{2}\), i.e., they are not isolated vertices, the new vertex \(z\) in \(G_{1}\oplus_{v,w}G_{2}\) is called an _articulation vertex_ of \(G_{1}\oplus_{v,w}G_{2}\), since \((G_{1}\oplus_{v,w}G_{2})-z\) has more connected components than \(G_{1}\oplus_{v,w}G_{2}\). For a graph \(G\), a maximal biconnected subgraph without any articulation vertex is called a _block_ or a _biconnected component_ of \(G\). The bounds of Theorem 25 for tree-width imply that the tree-width of a graph equals the maximum tree-width of its biconnected components. **Corollary 11**: _Let \(G\) be a graph. It holds that the tree-width of \(G\) equals the maximum tree-width of its biconnected components._  
Conversely, the following example shows that Corollary 11 does not hold for path-width.