## 5 Theoretical and bibliographical background
### The unicity of clique minimal separator decomposition  
[PERSON] [15] originally defined the decomposition step of a graph by a clique separator as follows:  
**Decomposition Step 5.4**: _Let \(S\) be a clique separator of \(G^{\prime}=(V^{\prime},E^{\prime})\), let \((S,A,B)\) be a partition of \(V^{\prime}\) such that no vertex in \(A\) is adjacent to a vertex in \(B\). Replace \(G^{\prime}\) by \(G^{\prime}_{1}=G^{\prime}(S\cup A)\) and \(G^{\prime}_{2}=G^{\prime}(S\cup B)\)._  
He remarked that the set of atoms obtained by repeatedly applying this decomposition step is not unique, giving a counterexample that is recalled in Figure 9, and left the problem of the unicity of the decomposition open. [PERSON] [19] solved this problem, showing that using clique minimal separators instead of clique separators ensures unicity of the decomposition (with the additional condition that each one of \(A\) and \(B\) contains a full component of \(S\) in \(G^{\prime}\) in the case of Decomposition Step 5.4). We present some elements of the proof of this result, which is associated in [19] with proofs of more complex results which make it difficult for non-specialists to follow. We first recall some definitions given in [19]. **Definition 5.5**: _A graph is prime if it is connected and has no clique separator (or equivalently, no clique minimal separator). A mp-subgraph of a graph \(G\) is a maximal prime subgraph of \(G\)._  
[PERSON] proved that the clique minimal separator decomposition of a graph \(G\) is the set of mp-subgraphs of \(G\) (Characterization 3.3). The proof of this characterization relies on the following property. **Property 5.6**: _Let \(G=(V,E)\) be a graph, let \(S\) be a clique of \(G\) having at least one full component in \(G\). Then there is a subset \(A\) of \(V\) such that \(S\subset A\) and \(G(A)\) is prime._  
Figure 9: A graph with different decompositions by clique separators. (a) Graph. (b) One decomposition, which is the unique decomposition by clique minimal separators. (c) Another decomposition. **Proof:** _(idea of the proof)_ The property holds if \(G\) is chordal since in that case, as \(S\) is a clique of \(G\) having a full component, say \(C\), in \(G\), there is a vertex \(x\) of \(C\) such that \(S\subseteq N_{G}(x)\) (this follows from the results in [4]), and therefore \(S\cup\{x\}\) is a clique and induces a prime graph. Let us show that it holds for any graph \(G\). Let \(G^{*}\) be the graph obtained from \(G\) by making each mp-subgraph of \(G\) into a clique. \(G^{*}\) is chordal and has the same mp-subgraphs as \(G\)[19]. There is a subset \(A\) of \(V\) such that \(S\subset A\) and \(G^{*}(A)\) is prime. Let \(B\) be a subset of \(V\) such that \(A\subseteq B\) and \(G^{*}(B)\) is a mp-subgraph of \(G^{*}\). Then \(S\subset B\) and \(G(B)\) is prime. \(\Box\) He also showed the following characterization, which is Characterization 3.3:  
**Characterization 5.7**: _The clique minimal separator decomposition of graph \(G\) is the set of mp-subgraphs of \(G\)._  
**Proof:** We suppose that the decomposition step which is used is Decomposition Step 5.4 with the additional condition that each one of \(A\) and \(B\) contains a full component of \(S\) in \(G^{\prime}\), which is more general than Decomposition Step 3.1. The proof goes by induction on the number \(n\) of vertices of the graph. The property trivially holds if \(n=1\). Suppose that it holds for any graph with at most \(n\) vertices. Let us show that it holds for a graph \(G=(V,E)\) with \(n+1\) vertices. The property trivially holds if \(G\) has no clique minimal separator. We suppose that \(G\) has a clique minimal separator \(S\). Let \((S,A,B)\) be a partition of \(V\) such that no vertex in \(A\) is adjacent to a vertex in \(B\) and each one of \(A\) and \(B\) contains a full component of \(S\) in \(G\). Let \(G_{1}=G(S\cup A)\) and \(G_{2}=G(S\cup B)\).