## 4 The Separator Structure in the Neighborhood of Vertex 1
### MLS on a non-chordal graph  
On a non-chordal graph, in general, an MLS execution does not end on a moplex and does not even end on a vertex of a moplex, even if the order on labels is total, as shown by Figure 6 for MCS. However, we show that if the order on labels is total then MLS does ends on an OCF-vertex. **Theorem 5.3**: _For any graph \(G\), any labeling structure \(\mathcal{L}\) and any \(\mathcal{L}\)-MLS ordering \(\alpha\) of \(G\), if the order on labels is total then \(\alpha(1)\) is an OCF-vertex of \(G\)._  
The proof of Theorem 5.3 uses the following Lemma, where for any vertices \(x\) and \(y\) of \(G\) such that \(\alpha^{-1}(x)\geq\alpha^{-1}(y)\), \(l_{x}(y)\) denotes the label of \(y\) just before numbering \(x\). **Lemma 5.4**: _We consider an MLS execution on a graph \(G\) computing \(\alpha\) and vertices \(u,v\) of \(G\) such that \(\alpha^{-1}(u)>\alpha^{-1}(v)\). If \(l_{u}(v)\preceq l_{u}(\alpha(1))\) and every neighbor \(t\) of \(v\) such that \(\alpha^{-1}(u)\geq\alpha^{-1}(t)>\alpha^{-1}(v)\) is a neighbor of \(\alpha(1)\) then \(l_{v}(v)=l_{v}(\alpha(1))\) and every neighbor \(t\) of \(\alpha(1)\) such that \(\alpha^{-1}(u)\geq\alpha^{-1}(t)>\alpha^{-1}(v)\) is a neighbor of \(v\)._  
**Proof:** At every step between numbering \(u\) and numbering \(v\), if the label of \(v\) is incremented then the label of \(\alpha(1)\) is incremented too, so by Properties (p1) and (p2) of Definition 3.1 the inequality \(l(v)\preceq l(\alpha(1))\) is preserved, and since \(l(v)\) is maximal just before numbering \(v\), \(l_{v}(v)=l_{v}(\alpha(1))\). Now if some vertex \(t\) numbered between \(u\) and \(v\) was a neighbor of \(\alpha(1)\) but not of \(v\) then the inequality would become \(l(v)\prec l(\alpha(1))\), which would be preserved until numbering \(v\), a contradiction. \(\Box\)  
**Proof:** (of Theorem 5.3) We define the partition of \(V\) into subsets \(T^{\prime}_{i}\), \(1\leq i\leq p^{\prime}\), which is a variant of the partition of \(V\) into thin slices. For any \(i\) in \([1,p^{\prime}]\),  
- \(t^{\prime}_{i}=\alpha(n)\) if \(i=1\), otherwise \(t^{\prime}_{i}\) is the first vertex numbered after \(c^{\prime}_{i-1}\) not belonging to \(N[C^{\prime}_{i-1}]\),  
- \(c^{\prime}_{i}=t^{\prime}_{i}\) if \(t^{\prime}_{i}\
ot\in N(\alpha(1))\), otherwise \(c^{\prime}_{i}\) is the first vertex numbered after \(t^{\prime}_{i}\) which does not belong to \(N(\alpha(1))\) (\(c^{\prime}_{p^{\prime}}=\alpha(1)\)),  
- \(C^{\prime}_{i}\) is the component of \((G,\alpha)\) containing \(c^{\prime}_{i}\) (\(C^{\prime}_{p^{\prime}}=\{\alpha(1)\}\)),- \(T^{\prime}_{i}\) is the set of vertices \(t\) such that \(\alpha^{-1}(t^{\prime}_{i})\geq\alpha^{-1}(t)\) and (if \(i<p^{\prime}\)) \(\alpha^{-1}(t)>\alpha^{-1}(t^{\prime}_{i+1}\)), so by definition, the subsets \(T^{\prime}_{i}\) are numbered in increasing order. Note that for any \(i\) in \([1,p^{\prime}]\)\(T^{\prime}_{i}\subseteq N(\alpha(1))\cup C^{\prime}_{i}\) and that there may be distinct \(i\), \(j\) such that \(C^{\prime}_{i}=C^{\prime}_{j}\), so \(p^{\prime}\) can be greater than the number of components of \((G,\alpha)\). We first show that for any \(i\) in \([1,p^{\prime}]\), \(l(\alpha(1))\) is maximum among labels of unnumbered vertices just before numbering \(t^{\prime}_{i}\). The proof goes by induction on \(i\). It obviously holds for \(i=1\). We suppose that it holds for some \(i<p^{\prime}\). \(l_{t^{\prime}_{i}}(t^{\prime}_{i+1})\preceq l_{t^{\prime}_{i}}(\alpha(1))\), and every neighbor \(t\) of \(t^{\prime}_{i+1}\) in \(T^{\prime}_{i}\) is a neighbor of \(\alpha(1)\) since by definition of \(t^{\prime}_{i+1}\), \(t\) cannot be in \(C^{\prime}_{i}\). By Lemma 5.4 with \(u=t^{\prime}_{i}\) and \(v=t^{\prime}_{i+1}\)\(l_{t^{\prime}_{i+1}}(t^{\prime}_{i+1})=l_{t^{\prime}_{i+1}}(\alpha(1))\), and since \(l(t^{\prime}_{i+1})\) is maximum at that step (because the order \(\preceq\) is total) \(l(\alpha(1))\) is maximum too. Now let \(y,z\in N(\alpha(1))\) such that \(\alpha^{-1}(y)>\alpha^{-1}(z)\).