# Correspondence between Multilevel Graph Partitions and Tree Decompositions
## 4 Correspondence between Multilevel Graph Partitioning and Tree Decompositions
### Correctness Proof
The boundary definition requires, that a node \(y\in C\) exists such that \(\{x,y\}\in E\) is an edge. As \(x\) is not part of a child bag, \(x\) is not on the boundary of any child cell. \(y\) can therefore not be part of a child cell. As \(y\in C\), \(y\) must be part of \(C\)'s separator. \(y\) is thus not part of \(X_{p}\). \(X\) is therefore the only bag to contain both \(x\) and \(y\). Removing \(x\) from \(X\) would therefore violate the edge requirement. The constructed tree decomposition therefore fulfills the small bag property. As we have proven all three requirements and both properties, we have proven the theorem. The proof that the multilevel partition constructed by TD2 MLP is valid is more involved. We therefore organize the proof into several lemmas. Theorem 3 contains the proof that the multilevel partition is valid. Lemmas 5, 6, and 7 are used in the proof of Theorem 3. Lemma 4 exists to prove Lemmas 5, 6, and 7. Lemma 4: _Let \(X\) be a bag and \(\mathcal{X}_{d}\) the set of descendant bags of \(X\). For every node \(x\in C_{X}\), no bag outside of \(\mathcal{X}_{d}\) contains \(x\)._  
Proof. : If \(X\) is the root bag, then no bag outside of \(\mathcal{X}_{d}\) exists and the lemma is trivially true. If \(X\) is not the root bag, a parent bag \(X_{p}\) exists. The cell \(C_{X}\) is by definition equal to \(\bigcup\mathcal{X}_{d}\setminus(X\cap X_{p})\). A node that is in \(X\) and in \(X_{p}\) can therefore not be part of \(C_{X}\). As \(x\in C_{X}\), \(x\) must be part of \(\bigcup\mathcal{X}_{d}\). \(x\) must therefore be part of a bag \(Y\) in \(\mathcal{X}_{d}\). Pick any bag \(Z\) outside of \(\mathcal{X}_{d}\). If \(Z\) contained \(x\), then the path requirement states that every bag on the path from \(Y\) to \(Z\) contains \(x\). Both \(X\) and \(X_{p}\) are on this path. However, nodes that are in \(X\) and \(X_{p}\) cannot be part of \(C_{X}\). This is a contradiction to \(x\in C_{X}\). As a consequence, \(Z\) cannot exist, which concludes the proof of the lemma. Lemma 5: _Let \(X\) and \(Y\) be two distinct bags. If \(Y\) is an ancestor of \(X\), then \(C_{X}\subseteq C_{Y}\)._  
Proof. : If \(Y\) is the root, then \(C_{Y}=V\) and \(C_{X}\subseteq C_{Y}\) trivially holds. In the following, assume that \(Y\) is not the root and has a parent \(Y_{p}\). Similarly, \(X\) has a parent \(X_{p}\). Further, let \(\mathcal{X}_{d}\) and \(\mathcal{Y}_{d}\) be the descendant bags of \(X\) and \(Y\). By construction, we know that \(C_{X}=\bigcup\mathcal{X}_{d}\setminus(X\cap X_{p})\) and \(C_{Y}=\bigcup\mathcal{Y}_{d}\setminus(Y\cap Y_{p})\). As \(X\) is a descendant of \(Y\), \(\mathcal{X}_{d}\subseteq\mathcal{Y}_{d}\). To conclude the proof, it is therefore sufficient to show that no node \(x\in C_{X}\) exists that is part of \(Y\cap Y_{p}\). Suppose that such a node \(x\) existed. In this case, \(x\) would be part of \(Y\), which is a bag outside of \(\mathcal{X}_{d}\), and thus is a contradiction with Lemma 4. We have thus proven that, if \(Y\) is an ancestor of \(X\), then \(C_{X}\subseteq C_{Y}\), which concludes the proof. Lemma 6: _If the cells \(C_{X}\) and \(C_{Y}\) share a node, then the bags \(X\) and \(Y\) are in an ancestry relationship._Proof. : Denote by \(x\) the shared node. From Lemma 4, we deduce that only descendant bags of \(X\) contain \(x\). As \(x\) is in \(C_{Y}\), we further conclude that there is a descendant bag \(Z\) of \(Y\) that contains \(x\). This means that \(Z\) is a descendant bag of \(X\) and of \(Y\). \(X\) and \(Y\) must therefore be in an ancestry relationship. **Lemma 7**. : _If an edge \(\{x,y\}\) exists such that \(x\in C_{X}\) and \(y\in C_{Y}\), then the bags \(X\) and \(Y\) are in an ancestry relationship._  
Proof. : The edge requirement implies that a bag \(Z\) exists that contains \(x\) and \(y\). Using Lemma 4, we can conclude that \(Z\) is a descendant of \(X\) as \(x\in C_{X}\). Similarly, using the same lemma, we can conclude that \(Z\) is a descendant of \(Y\) as \(y\in C_{Y}\). \(Z\) is thus a descendant of \(X\) and \(Y\).