# Properties and Recognition of Atom Graphs
## 4 Atom Graphs Are Perfect
\(XY\) is an edge of \(AG(G)\) if \(C_{XY\cap Y}(X)\
eq C_{X\cap Y}(Y)\), which is still equivalent to \(C_{X\cap Y}(Y)\cap(X\setminus Y)=\emptyset\). Let \(C=C_{XY\cap Y}(Y)\). It is sufficient to show that \(N(C_{S}(Y))\subseteq Y\Leftrightarrow C\cap(X\setminus Y)=\emptyset\). First, note that as \(N(C_{S}(Y))\subseteq S\subseteq X\), we have \(N(C_{S}(Y))\subseteq X\), and that as \(C_{S}(X)\
eq C_{S}(Y)\), we have \(X\cap Y\subseteq S\), and therefore \(C_{S}(Y)\subseteq C\subseteq V\setminus(X\cap Y)\). \(\Rightarrow\): We assume that \(N(C_{S}(Y))\subseteq Y\). Then, \(N(C_{S}(Y))\subseteq X\cap Y\), with \(C_{S}(Y)\) being a connected subset of \(V\setminus(X\cap Y)\), so \(C=C_{S}(Y)\) and therefore \(C\cap(X\setminus Y)\subseteq C_{S}(Y)\cap X=\emptyset\). \(\Leftarrow\): We now assume that \(N(C_{S}(Y))\
ot\subseteq Y\). Let \(x\in N(C_{S}(Y))\setminus Y\). \(x\in X\setminus Y\), and as \(x\
ot\in X\cap Y\) and \(x\) has a neighbor in \(C_{S}(Y)\) with \(C_{S}(Y)\subseteq C\), \(x\in C\). Hence, \(x\in C\cap(X\setminus Y)\), and therefore \(C\cap(X\setminus Y)\
eq\emptyset\). (b) As \(N(C_{S}(Y))\subseteq S\subseteq Y\), by a) \(XY\) is an edge of \(AG(G)\). (c) We assume for contradiction that \(S\subseteq X\cap X^{\prime}\), \(C_{S}(X)=C_{S}(X^{\prime})\), \(Y\) is adjacent to \(X\) but not to \(X^{\prime}\) in \(AG(G)\) and \(C_{S}(X)\
eq C_{S}(Y)\). By (a) on \(X\) and \(Y\), \(N(C_{S}(Y))\subseteq Y\), and by (a) on \(X^{\prime}\) and \(Y\), \(N(C_{S}(Y))\
ot\subseteq Y\), a contradiction. Property 9: _Let \(G\) be a graph and let \(\mu\) be a chordless cycle of \(AG(G)\) of length at least \(4\); then either \(\mu\) is of length \(4\) and its four edges are associated with the same clique minimal separator or there is an integer \(k\geq 2\) such that \(\mu\) is of length \(2k\), there are exactly \(k\) distinct clique minimal separators associated with the edges of \(\mu\) which are pairwise non-inclusive and each such separator is associated with two consecutive edges of \(\mu\).__In both cases, for each set of consecutive edges \(XY\) and \(YZ\) of \(\mu\) associated with the same clique minimal separator \(S\), \(C_{S}(X)=C_{S}(Z)\)._  
Proof. : Let \(AB\) be an edge of \(\mu\) such that \(A\cap B\) is inclusion-minimal among the clique minimal separators associated with the edges of \(\mu\) and let \(S=A\cap B\). Let us first prove the following property \(P_{1}\). \(P_{1}\): for each pair \(\{X,Y\}\) of nodes of \(\mu\) such that \(C_{S}(X)\
eq C_{S}(Y)\), the following propositions are equivalent:  
(1) \(XY\) is an edge of \(\mu\),  
(2) \(X\cap Y=S\),  
(3) \(S\subseteq X\cap Y\). \(1\Rightarrow 2\): as \(C_{S}(X)\
eq C_{S}(Y)\)\(X\cap Y\subseteq S\), and by the minimality of \(S\)\(X\cap Y\
ot\subset S\), so \(X\cap Y=S\). \(2\Rightarrow 3\) is evident. \(3\Rightarrow 1\): by Lemma 3 (b) \(XY\) is an edge of \(AG(G)\), and therefore of \(\mu\) since \(\mu\) is chordless. By Lemma 2, there is an edge \(A^{\prime}B^{\prime}\) of \(\mu\) such that \(C_{S}(B)=C_{S}(B^{\prime})\) and \(A^{\prime}\cap B^{\prime}\subseteq S\), with \(A\), \(B\), \(B^{\prime}\), \(A^{\prime}\) in this order on \(\mu\). By the minimality of \(S\), \(A^{\prime}\cap B^{\prime}=S\). As \(AB\) is an edge of \(AG(G)\), \(C_{S}(A)\
eq C_{S}(B)\), and therefore \(C_{S}(A)\
eq C_{S}(B^{\prime})\). As \(S\subseteq A\cap B^{\prime}\), by \(P_{1}\)\(AB^{\prime}\) is an edge of \(\mu\). It follows that \(B=B^{\prime}\) or \(A=A^{\prime}\). We assume, without loss of generality, that \(B=B^{\prime}\). By \(P_{1}\) again, as \(S\subseteq A\cap A^{\prime}\) and \(AA^{\prime}\) is not an edge of \(\mu\), \(C_{S}(A)=C_{S}(A^{\prime})\). Let \(D\) be the neighbor of \(A\) on \(\mu\) different from \(B\). _First case_ : \(C_{S}(D)=C_{S}(B)\)  
As \(C_{S}(A)\
eq C_{S}(D)\) and \(AD\) is an edge of \(\mu\), by \(P_{1}\)\(A\cap D=S\). Hence, as \(C_{S}(D)\
eq C_{S}(A^{\prime})\) and \(S\subseteq D\cap A^{\prime}\), by \(P_{1}\)\(DA^{\prime}\) is an edge of \(\mu\) and \(D\cap A^{\prime}=S\).