## 4 The Separator Structure in the Neighborhood of Vertex 1
### A technical lemma  
To prove Lemma 4.6, we will use the following notations and preliminary Lemmas. **Notations 4.7**: _For any execution of MLS on any graph \(G\) computing ordering \(\alpha\) and any vertices \(x\) and \(y\) of \(G\) such that \(\alpha^{-1}(x)\geq\alpha^{-1}(y)\),_  
_(i) \(l_{x}(y)\) denotes the label of \(y\) just before numbering \(x\),_  
_(ii) \(NN_{x}(y)\) denotes the set of Numbered Neighbors of \(y\) just before numbering \(x\), i.e., \(NN_{x}(y)=\{z\in N(y)\mid\alpha^{-1}(z)>\alpha^{-1}(x)\}\)._  
_The subscript will be omitted when the considered step is clear from the context._  
The following Lemma is given in [12]. **Lemma 4.8**: _([12]) At any step of an execution of MLS on a graph \(G\), for any unnumbered vertices \(u,v\) of \(G\),_  
_(i) if \(NN(u)=NN(v)\) then \(l(u)=l(v)\),_  
_(ii) if \(NN(u)\subset NN(v)\) then \(l(u)\prec l(v)\)._  
**Lemma 4.9**: _For any MLS ordering \(\alpha\) of a chordal graph, \(\forall i\in[1,p]\),_  
_(1) \(NN_{d_{i}}(d_{i})=NN_{d_{i}}(\alpha(1))\subseteq N(D_{i})\),_  
_(2) if \(i<p\) then \(\alpha^{-1}(t_{i})\geq\alpha^{-1}(d_{i})>\alpha^{-1}(t_{i+1})\),_  
_(3) \(NN_{t_{i}}(t_{i})=NN_{t_{i}}(\alpha(1))\)._  
**Proof:** (1) \(NN_{d_{i}}(d_{i})\subseteq NN_{d_{i}}(\alpha(1))\) by definition of \(d_{i}\) and \(NN_{d_{i}}(d_{i})\
ot\subset NN_{d_{i}}(\alpha(1))\) (otherwise by Lemma 4.8\(l_{d_{i}}(d_{i})\prec l_{d_{i}}(\alpha(1))\), which contradicts the choice of \(d_{i}\) at that step). Hence \(NN_{d_{i}}(d_{i})=NN_{d_{i}}(\alpha(1))\subseteq N[D_{i}]\cap N(\alpha(1))=N(D _{i})\). (2) We suppose that \(i<p\). By definition of \(d_{i}\) and \(t_{i}\), \(\alpha^{-1}(t_{i})\geq\alpha^{-1}(d_{i})\). Let us show that \(\alpha^{-1}(d_{i})>\alpha^{-1}(t_{i+1})\). If \(t_{i+1}\
ot\in N(\alpha(1))\) then \(t_{i+1}=d_{i+1}\) and we are done since by definition of \(d_{i}\), \(\alpha^{-1}(d_{i})>\alpha^{-1}(d_{i+1})\). Otherwise, assume for contradiction that \(\alpha^{-1}(t_{i+1})>\alpha^{-1}(d_{i})\). Then \(t_{i+1}\in NN_{d_{i}}(\alpha(1))\), and by statement 1 we have: \(NN_{d_{i}}(\alpha(1))\subseteq N(D_{i})\subseteq V-T_{i+1}\), so \(t_{i+1}\
ot\in T_{i+1}\), a contradiction. (3) For any \(j<i\), \(NN_{t_{i}}(t_{i})\cap D_{j}=\emptyset\) because \(N(t_{i})\cap D_{j}=\emptyset\) (since \(T_{i}\cap N(D_{j})=\emptyset\)), and for any \(j\geq i\), \(NN_{t_{i}}(t_{i})\cap D_{j}=\emptyset\) because by 2), \(\forall t\in T_{j}\)\(\alpha^{-1}(t_{i})\geq\alpha^{-1}(t_{j})\geq\alpha^{-1}(t)\). It follows that \(NN_{t_{i}}(t_{i})\subseteq NN_{t_{i}}(\alpha(1))\), and we show the equality as above for \(d_{i}\). \(\Box\)  
It is easy to show the following lemma:  
**Lemma 4.10**: _If \(G\) is a chordal graph, \(\mu\) a chordless path in \(G\) and \(z\) a vertex of \(G\) not belonging to \(\mu\) and seeing both extremities of \(\mu\), then \(z\) sees every vertex of \(\mu\)._  
**Lemma 4.11**: _Let \(G\) be a chordal graph, let \(\alpha\) be an MLS ordering of \(G\), and for \(i=1,2,...,p\), let \(s\in S_{i}\) such that \(\alpha^{-1}(d_{i})>\alpha^{-1}(s)\). Since \(s\in S_{i}\), there exists a chordless path \(\mu\) from \(d_{i}\) to \(s\) such that every internal vertex of \(\mu\) belongs to \(D_{i}\). Then the following property \(P\) holds just after processing \(d_{i}\) and remains true until numbering \(s\)._  
\(P\) _: there is a vertex_ \(v\) _of_ \(\mu\) _such that every vertex of_ \(\mu[v,s]\) _is unnumbered,_ \(NN(\alpha(1))\subset NN(v)\) _and_ \(\forall t\in\mu[v,s]-\{v\}\)_,_ \(NN(t)=NN(\alpha(1))\)_._  
**Proof:** Let us show that \(P\) holds just after processing \(d_{i}\). \(NN_{d_{i}}(d_{i})=NN_{d_{i}}(\alpha(1))\) by Lemma 4.9, so \(NN_{d_{i}}(\alpha(1))\subseteq N(d_{i})\). Also \(NN_{d_{i}}(\alpha(1))\subseteq N(s)\) since, as \(\alpha\) is a peo of \(G\), \(N(\alpha(1))\) is a clique of \(G\).