## 4 The Separator Structure in the Neighborhood of Vertex 1
### A technical lemma
It follows by Lemma 4.10 that for any vertex \(t\) of \(\mu\), \(NN_{d_{i}}(\alpha(1))\subseteq N(t)\), so \(NN_{d_{i}}(\alpha(1))\subseteq NN_{d_{i}}(t)\), and as the reverse inclusion holds by definition of \(d_{i}\) and \(S_{i}\), \(NN_{d_{i}}(t)=NN_{d_{i}}(\alpha(1))\). After processing \(d_{i}\), \(NN(\alpha(1))\) is unchanged and \(P\) is true, taking as vertex \(v\) the vertex of \(\mu\) next to \(d_{i}\) (which is the only vertex of \(\mu\) seeing \(d_{i}\) since \(\mu\) is chordless). Let us show that \(P\) is true after processing some vertex \(w\), \(\alpha^{-1}(d_{i})>\alpha^{-1}(w)>\alpha^{-1}(s)\). _First case:_\(w\
ot\in N(\alpha(1))\). If no vertex of \(\mu[v,s]\) sees \(w\) then \(w\
ot\in\mu[v,s]\) and \(P\) remains true with the same vertex \(v\), otherwise \(P\) remains true, taking as new vertex \(v\) the last vertex of \(\mu[v,s]\) seeing \(w\). _Second case:_\(w\in N(\alpha(1))\). \(ws\) is an edge of \(G\), as \(N(\alpha(1))\) is a clique. We get from edge \(ws\) and path \(\mu[v,s]\) a \(wv\)-path such that every internal vertex \(t\) is unnumbered and satisfies \(NN(t)=NN(\alpha(1))\subset NN(v)\), so by Lemma 4.8\(l(t)\prec l(v)\). By Property 3.2, this execution of MLS on chordal graph \(G\) can be seen as an execution of MLSM, according to which \(wv\) will be an edge of \(H\) with \(H=G_{\alpha}^{+}=G\). It follows that \(w\) sees \(v\) in \(G\). By Lemma 4.10\(w\) sees every vertex of \(\mu[v,s]\). It follows that when processing \(w\), \(w\) is added to \(NN(\alpha(1))\) as well as to \(NN(t)\) for every vertex \(t\) of \(\mu[v,s]\), and \(P\) remains true with the same vertex \(v\). \(\Box\)  
**Lemma 4.12**: _For any MLS ordering \(\alpha\) of a chordal graph, \(\forall i\in[1,p-1],\forall s\in S_{i}\), \(\alpha^{-1}(s)>\alpha^{-1}(t_{i+1})\)._  
**Proof:** Suppose there is some \(s\in S_{i}\) such that \(\alpha^{-1}(t_{i+1})>\alpha^{-1}(s)\). Then by Lemma 4.9\(\alpha^{-1}(d_{i})>\alpha^{-1}(t_{i+1})>\alpha^{-1}(s)\). Lemma 4.11 ensures the existence of some vertex \(v\) such that \(NN_{t_{i+1}}(\alpha(1))\subset NN_{t_{i+1}}(v)\), so by Lemma 4.9\(NN_{t_{i+1}}(t_{i+1})\subset NN_{t_{i+1}}(v)\) and by Lemma 4.8\(l_{t_{i+1}}(t_{i+1})\prec l_{t_{i+1}}(v)\), which contradicts the choice of \(t_{i+1}\) at that step. \(\Box\)  
**Lemma 4.13**: _For any MLS ordering \(\alpha\) of a chordal graph, if the order on labels is total then \(\forall i\in[1,p-1]\), \(\forall d\in D_{i}\), \(\alpha^{-1}(d)>\alpha^{-1}(t_{i+1})\)._  
**Proof:** Suppose there is some \(d\in D_{i}\) such that \(\alpha^{-1}(t_{i+1})>\alpha^{-1}(d)\). We can choose \(d\) as the first vertex of \(D_{i}\) numbered after \(t_{i+1}\). Just before numbering \(t_{i+1}\), \(l(t_{i+1})\) is maximum (since the order \(\preceq\) is total) with \(l_{t_{i+1}}(t_{i+1})=l_{t_{i+1}}(\alpha(1))\) by Lemmas 4.9 and 4.8, so \(l_{t_{i+1}}(d)\preceq l_{t_{i+1}}(\alpha(1))\). As by Lemma 4.12, every vertex of \(N(D_{i})\) is numbered before \(t_{i+1}\), \(l(d)\) remains equal to \(l_{t_{i+1}}(d)\) until \(d\) is numbered. We thus only have to prove that \(l(\alpha(1))\) is incremented before numbering \(d\). This will lead to a contradiction, since \(\alpha(1)\) is numbered last. If \(t_{i+1}\in N(\alpha(1))\), \(l(\alpha(1))\) is incremented when numbering \(t_{i+1}\) and we are done. If \(t_{i+1}\
otin N(\alpha(1))\), \(t_{i+1}=d_{i+1}\). By Property 4.14, \(S_{i+1}\) is not empty, so let \(s\in S_{i+1}\). \(\alpha^{-1}(d_{i+1})>\alpha^{-1}(s)\), and by Lemma 4.11, until numbering \(s\), there is some unnumbered vertex \(v\) such that \(NN(\alpha(1))\subset NN(v)\), so by Lemma 4.8\(l(\alpha(1))\prec l(v)\), hence \(l(d)\prec l(v)\). This implies that \(\alpha^{-1}(s)>\alpha^{-1}(d)\) and as \(l(\alpha(1))\) is incremented when processing \(s\), it is incremented before numbering \(d\). \(\Box\)  
As Lemma 4.6 a) can be rewritten as \(NN_{d_{i}}(\alpha(1))\subseteq NN_{d_{i}}(d_{i})\), Lemma 4.6 directly follows from Lemmas 4.9, 4.12 and 4.13.