# Computing a Clique Tree with the Algorithm Maximal Label Search
## 4 Clique Tree of the Complement Graph
: _The algorithm complement-DCL-MLS-CliqueTree is correct._  
An ordering computed by the algorithm complement-DCL-MLS-CliqueTree is a \(\text{Rev}(\mathcal{L})\)-MLS ordering of \(G\), and therefore, by Theorem 5 a \(\mathcal{L}\)-MLS ordering of \(H\), which is a PEO of \(H\). To prove Theorem 6, we will use the following Lemma. **Lemma 4**. : _In an execution of complement-DCL-MLS-CliqueTree, for each \(i\) in \([1,n-1]\) and each \(y\) in \(V\) such that \(\alpha^{-1}(y)\leq i\), at the beginning of iteration \(i\), the following propositions are equivalent:_  
1. \(N_{H}^{\alpha+}[x_{i+1}]\subseteq N_{H}^{\alpha,i}(y)\)_,_
2. _prev-min-label_\(=label(y)\)_,_
3. \(N_{H}^{\alpha+}[x_{i+1}]=N_{H}^{\alpha,i}(y)\)_._  
**Proof. ** (1) \(\Rightarrow\) (2): We suppose that \(N_{H}^{a+}[x_{i+1}]\subseteq N_{H}^{a,i}(y)\). Then, \(N_{G}^{a,i}(y)\subseteq N_{G}^{a,i}(x_{i+1})\), and therefore, by Lemma 1, \(label(y)\preceq label(x_{i+1})=\textit{prev-min-label}\). Moreover, \(label(y)\
ot<\textit{prev-min-label}\) since \(label(y)\) and \(\textit{prev-min-label}\) are the labels of \(y\) and \(x_{i+1}\), respectively, at the beginning of iteration \(i+1\). Hence, \(\textit{prev-min-label}=label(y)\). (2) \(\Rightarrow\) (3): We suppose that \(\textit{prev-min-label}=label(y)\). Then, the label of \(y\) is not increased during iteration \(i+1\) (otherwise, it would have been strictly smaller than the label of \(x_{i+1}\) at the beginning of iteration \(i+1\)). It follows that \(y\) is not adjacent to \(x_{i+1}\) in \(G\) and therefore is adjacent to \(x_{i+1}\) in \(H\). As \(\alpha\) is a PEO of \(H\), \(N_{H}^{a,i}(y)\subseteq N_{H}^{a+}[x_{i+1}]\). Moreover, \(N_{H}^{a,i}(y)\
ot<N_{H}^{a+}[x_{i+1}]\), since otherwise, \(N_{G}^{a,i}(x_{i+1})\subset N_{G}^{a,i}(y)\), and therefore, by Lemma 1, \(\textit{prev-min-label}\prec label(y)\). Hence, \(N_{H}^{a+}[x_{i+1}]=N_{H}^{a,i}(y)\). (3) \(\Rightarrow\) (1) is evident. \(\Box\)  
**Proof. ** (of Theorem 6) Let \(\alpha=(x_{1},\ldots,x_{n})\) be the ordering computed by an execution of complement-DCL-MLS-CliqueTree on input \(G\) and \(\mathcal{L}\), and let \(H=\overline{G}\). Let us show that it is a PMO of \(H\), i.e., a MCComp PEO of \(H\) by Characterization 3. As \(\alpha\) is an MLS ordering of \(H\), it is a PEO of \(H\). Let \(i\in[1,n-1]\). We suppose that \(N_{H}^{a+}[x_{i+1}]\) is not a maximal clique of \(H\). Let us show that it is equal to \(N_{H}^{a+}(x_{i})\). As \(N_{H}^{a+}[x_{i+1}]\) is not a maximal clique of \(H\), there is a vertex \(y\), such that \(\alpha^{-1}(y)\leq i\) and \(N_{H}^{a+}[x_{i+1}]\subseteq N_{H}^{a,i}(y)\), and therefore, by Lemma 4, \(\textit{prev-min-label}=label(y)\) at the beginning of iteration \(i\) in this execution. It follows by the condition on the choice of \(x\) that \(\textit{prev-min-label}=label(x_{i})\) and, therefore, by Lemma 4 that \(N_{H}^{a+}[x_{i+1}]=N_{H}^{a+}(x_{i})\). It remains to show that condition \(\textit{prev-min-label}\
eq label(x)\) correctly detects new cliques. It is evident at iteration \(n\). For each iteration \(i\) with \(i<n\), it immediately follows from Lemma 4, as the condition to start a new clique is \(K_{s}\
eq S\), i.e., \(N_{H}^{a+}[x_{i+1}]\
eq N_{H}^{a,i}(x)\) by Invariant 2 (e). \(\Box\)  
**Example 3**. : _Let \(G\) be the complement graph of the graph \(H\) shown in Figure 1. An execution of the algorithm complement-DCL-MLS-CliqueTree on \(G\) and labeling structure \(\mathcal{L}_{LexDFS}\) computing ordering \((a,b,c,d,e,f)\) is shown in Figure 3. For each vertex \(x\), the number \(\alpha^{-1}(x)\) and the final label of \(x\) are indicated. At the beginning of Iteration 4, \(label(a)=label(b)=(5)\) and \(label(c)=label(d)=(6)\), with \((6)\prec(5)\) according to labeling structure \(\mathcal{L}_{LexDFS}\) and \(\textit{pre-min-label}=()\); vertex \(d\) is chosen, and new clique \(K^{\prime}\) is started at Iteration 4 as desired.