# Correspondence between Multilevel Graph Partitions and Tree Decompositions
## 4 Correspondence between Multilevel Graph Partitioning and Tree Decompositions
### Correctness Proof
\(X\) and \(Y\) are therefore in an ancestry relationship. **Theorem 3**. : _Given a rooted tree decomposition with leaf property, TD2 MLP constructs a multilevel partition._  
Proof. : We need to prove that the constructed multilevel partition fulfills the four multilevel partition requirements. We need to show that the cell corresponding to the root bag is \(V\), that no cell is empty, that touching cells are ordered by inclusion, and that cells that are subset of another cell are in an ancestry relationship. From the node requirement, we know that every node is in a bag. The cell corresponding to the root bag is defined as the union of all bags. This union is therefore \(V\). To show that no cell is empty, we need to show that \((\bigcup\mathcal{X}_{d})\setminus(X\cap X_{p})\) is never empty. We need to show that a node \(x\in\bigcup\mathcal{X}_{d}\) exists that is not part of \(X\cap X_{p}\). There is at least one descendant bag \(Y\) of \(X\) that is a leaf. The leaf property states that a node \(x\in Y\) exists that is not part of \(Y\)'s parent bag \(Y_{p}\). If \(X=Y\), then we are finished. Otherwise, \(Y_{p}\) is on the path from \(Y\) to \(X_{p}\). As \(x\in Y\) but \(x\
ot\in Y_{p}\), it follows from the path property that \(x\
ot\in X_{p}\). However, \(x\) is in \(\bigcup\mathcal{X}_{d}\). We conclude that the cell is not empty. We show that touching cells are ordered by inclusion. Denote by \(X\) and \(Y\) two bags corresponding to a pair of touching cells \(C_{X}\) and \(C_{Y}\). As \(C_{X}\) and \(C_{Y}\) touch, they share a node or an edge exists with endpoints in \(C_{X}\) and \(C_{Y}\). If they share a node, we conclude using Lemma 6 that \(X\) and \(Y\) are in an ancestry relationship. Otherwise, if an edge exists with endpoints in \(C_{X}\) and \(C_{Y}\), we conclude using Lemma 7 that \(X\) and \(Y\) are in an ancestry relationship. From Lemma 5, it follows that, as \(X\) and \(Y\) are in an ancestry relationship, \(C_{X}\) and \(C_{Y}\) are ordered by inclusion. Finally, we need to show that if \(C_{X}\subsetneq C_{Y}\), \(Y\) is an ancestor of \(X\), and if \(C_{X}=C_{Y}\), \(X\) and \(Y\) are in an ancestry relationship. If \(C_{X}=C_{Y}\), then the cells share a node and thus using Lemma 6 we conclude that \(X\) and \(Y\) are in an ancestry relationship. Similarly, we can argue that, if \(C_{X}\subsetneq C_{Y}\), a node is shared and therefore \(X\) and \(Y\) are in an ancestry relationship. This means that either \(Y\) is a descendant or an ancestor of \(X\). We show by contradiction, that \(Y\) is an ancestor. Assume that \(Y\) was a descendant. In this case, we can conclude using Lemma 5 that \(C_{Y}\subseteq C_{X}\). This is a contradiction with \(C_{X}\subsetneq C_{Y}\). \(Y\) must therefore be an ancestor. Theorem 3 requires that the given rooted tree decomposition fulfills the leaf property. This is necessary to prove that the constructed cells are not empty. Fortunately, every rooted tree decomposition can easily be made to fulfill the leaf property by removing the offending and superfluous bags.