# Correspondence between Multilevel Graph Partitions and Tree Decompositions
## 4 Correspondence between Multilevel Graph Partitioning and Tree Decompositions
### Correctness Proof  
It remains to formally prove our theorem. In Theorems 2 and 3 in this section, we first show that the two algorithms are correct. In Section 4.6, we then show that they form a bijection. Theorem 2: _Given a multilevel partition, MLP2 TD constructs a rooted tree decomposition with leaf and small bag properties._  
Proof: We need to show that the three requirements laid out in the tree decomposition definition are fulfilled by the constructed tree decomposition. Further, we need to show that the leaf and the small bag properties hold. We first show that the node requirement is fulfilled, i.e., that every node is in a bag. A node \(v\) in a cell \(C\) is either in \(C\)'s separator \(S_{C}\) or in a child of \(C\). By applying this observation iteratively and using that the number of cells is finite, we conclude that every node that is in some cell is in some separator. As every cell's separator is part of its constructed bag, every node in a cell is in a bag. Further, as every node is in the root cell \(V\), we conclude that every node is in some separator and thus in some bag. Next, we prove that the edge requirement is fulfilled. We need to show that for every edge \(\{u,v\}\) there exists a bag \(X\) such that \(u\) and \(v\) are part of \(X\). As touching cells are ordered by inclusion, there is a cell \(C_{u}\) that contains \(u\) such that no child of \(C_{u}\) contains \(u\). \(u\) is in the separator of \(C_{u}\) and thus in the bag corresponding to \(C_{u}\). Let \(C_{v}\) be analogously a cell that contains \(v\) such that no child of \(C_{v}\) contains \(v\). If \(C_{u}=C_{v}\), then the bag corresponding to \(C_{u}\) is the required \(X\). Otherwise, we observe that the existence of \(\{u,v\}\) implies that \(C_{u}\) and \(C_{v}\) touch each other. The multilevel partition definition thus requires that \(C_{u}\) and \(C_{v}\) are ordered by inclusion. Assume without loss of generality that \(C_{u}\subseteq C_{v}\). Further, the existence of \(\{u,v\}\) implies that \(v\) is on the boundary of \(C_{u}\) and therefore in the bag corresponding to \(C_{u}\). The bag corresponding to \(C_{u}\) is therefore the required bag \(X\). In the next paragraph, we verify that the path requirement holds. We need to show that for every node \(x\) and every pair of bags \(X_{1}\) and \(X_{2}\) that include \(x\), \(x\) is part of all bags on the path from \(X_{1}\) to \(X_{2}\)The node \(x\) can only be in one cell's separator. Denote this cell's bag by \(X_{S}\). If \(x\) is on the boundary of a cell, \(x\) is on the boundary or separator of the cell's parent, and by extension \(x\) is part of the cell's parent's bag. As \(x\) is part of \(X_{1}\), \(x\) is either on the boundary or the separator of the corresponding cell. If it is on the boundary, \(x\) is also included in the parent bag of \(X_{1}\). By applying this argument iteratively, we conclude that \(x\) is in all bags of the path from \(X_{1}\) to \(X_{S}\). Similarly, \(x\) is in all bags of the path from \(X_{2}\) to \(X_{S}\). As \(X_{S}\) is unique, we conclude that all bags on the path from \(X_{1}\) to \(X_{2}\) contain \(x\). Next, we verify that the leaf property is fulfilled. Denote by \(C\) some non-root cell without child and by \(C_{p}\) its parent cell. As \(C\) is non-empty by definition and \(S_{C}=C\) by definition, there exists a node \(x\in S_{C}\). By definition, as \(x\in C\), \(x\) is not in the separator of \(C_{p}\). Further, as \(x\) in \(C_{p}\), it is not on the boundary of \(C_{p}\). As a consequence, \(x\) is part of the bag corresponding to \(C\) but not in the bag corresponding to \(C_{p}\). Finally, we prove the small bag property. Let \(X\) be a bag and \(x\) a node in \(X\) with the required properties. This means that there is a parent bag \(X_{p}\) such that \(x\in X_{p}\). Further, we know that no child bag of \(X\) contains \(x\). As \(x\in X_{p}\), \(x\) cannot be in the separator of \(C\). \(x\) is therefore on the boundary of \(C\).