## 4 The Separator Structure in the Neighborhood of Vertex 1
### Results on the separator structure  
Our main result is that if there are several minimal separators \(S_{1},...S_{k}\) in this neighborhood, then there is an inclusion order \(S_{1}\subseteq....\subseteq S_{k}\) on these separators:  
**Theorem 4.1**:
* _For any chordal graph_ \(H\) _and any MLS ordering_ \(\alpha\) _of_ \(H\)_, the minimal separators of_ \(H\) _included in_ \(N(\alpha(1))\) _are totally ordered by inclusion._
* _For any graph_ \(G\) _and any MLSM ordering_ \(\alpha\) _of_ \(G\)_, the minimal separators of_ \(G\) _included in_ \(N(\alpha(1))\) _are totally ordered by inclusion._  
**Example 4.2**: _In Figure 4, describing an execution of MCS on a chordal graph, the substars of \(1\) are \(\{8\}\) and \(\{3,8\}\); \(\{8\}\subseteq\{3,8\}\)._  
In order to prove Theorem 4.1, we need to examine how the search algorithms scan the various connected components defined by these separators. We will need to introduce some notations and definitions in order to describe this. Let us first explain the structure of the neighborhood of vertex 1, as illustrated by Figure 4.  
* The neighborhood of 1 contains minimal separators \(A_{1},...,A_{k}\), which are the substars of 1. In our example from Figure 4, \(A_{1}=\{8\}\) and \(A_{2}=\{3,8\}\). * The removal of \(N[1]\) defines connected components. In our example, \(C_{1}=\{5,7\}\), \(C_{1}^{\prime}\{6\}\), \(C_{2}=\{4\}\). Figure 4: The slices defined by an execution of MCS on a chordal graph. The substars of \(1\) are \(\{8\}\) and \(\{3,8\}\). * The neighborhoods of these components are the substars of 1: \(N(C_{1})=N(C_{1}^{\prime})=A_{1}=\{8\}\); \(N(C_{2})=A_{2}=\{3,8\}\). Thus with each substar is associated at least one of these components; when there are several components for the same substar, we will need to group them into what we call _super-components_: \(T_{1}=C_{1}\cup C_{1}^{\prime}=\{5,6,7\}\) is a super-component. * We will see that in some cases, the MLS algorithms will first number all the vertices of the super-component \(T_{1}\) which corresponds to the smallest substar \(A_{1}\) as well as this substar. It will then go on to number the super-component \(T_{2}\) which corresponds to the second smallest substar \(A_{2}\) as well as what is left of this substar, and so forth. This is the case in our example: substar \(\{8\}\) along with super-component \(T_{1}=\{5,6,7\}\) will be numbered first (from \(8\) to \(5\)), then super-component \(T_{2}=\{4\}\) will be numbered along with what is left of substar \(\{3,8\}\), which is \(\{3\}\), thus numbering from \(4\) to \(3\). We will call these numbering classes slices. * The largest substar, \(A_{k}\), defines a connected component which contain vertex 1, as well as the neighbors of 1 which do not belong to any substar (\(2\) in our example). This component (\(\{1,2\}\) in our example) defines our slice of largest number, and we will see that it defines a complex. We will now give precise notations for these notions:  
**Notations 4.3**: _For any graph \(G=(V,E)\) and any ordering \(\alpha\) on \(V\),_  
* \(a\) component \(C_{i}\) _is a connected component of_ \(G(V-N(\alpha(1)))\)_._
* \(a\) super-component \(D_{i}\) _is the union of all components with a common neighborhood._
* \(p\) _denotes the number of super-components_
* \((D_{1},D_{2},...,D_{p})\) _denotes the sequence of the super-components ordered as follows:_ \(\forall i\in[1,p-1]\)_,_ \(\alpha^{-1}(d_{i})>\alpha^{-1}(d_{i+1})\)_, where_ \(d_{i}\) _denotes the vertex of_ \(D_{i}\) _with maximum number (_\(\alpha^{-1}(d_{i})=max\{\alpha^{-1}(d),d\in D_{i}\}\)_)._
* _the slices are the subsets_ \(T_{1}\)_,_ \(T_{2}\)_,...,_ \(T_{p}\) _of_ \(V\) _partitioning_ \(V\) _as follows:_ \(\forall i\in[1,p]\)_,_ \(T_{i}=D_{i}\cup S_{i}\)_, where_ \(S_{i}=N(D_{i})-(\cup_{1\leq j<i}N(D_{j}))=N(D_{i})-(\cup_{1\leq j<i}S_{j})\)_, and_ \(t_{i}\) _denotes the vertex of_ \(T_{i}\) _with maximum number.