# Properties and Recognition of Atom Graphs
## 5 Atom Graph and Clique Graph of a Chordal Graph  
The atom graph of a chordal graph \(G\) is a subgraph of its clique graph with the same node set. These two graphs may be equal. It is the case if \(G\) is a block graph by Lemma 6 below, or the graph obtained from a \(C_{4}\) by adding a chord, which is not a block graph. We have the following characterization. Figure 4: A graph and its atom graph having an induced \(C_{4}\) whose edges are associated with two distinct clique minimal separators (\(\{2\}\) and \(\{7\}\)). Figure 3: A graph and its atom graph having an induced \(C_{4}\) whose edges are associated with the same clique minimal separator \(S\). **Characterization 9**. : _Let \(G\) be a connected chordal graph. The following propositions are equivalent (\(C_{S}(A)\) is defined in Notation 1):_  
1. \(AG(G)=CG(G)\)_,_
2. _for each minimal separator_ \(S\) _of_ \(G\) _and each maximal clique_ \(A\) _of_ \(G\)_,_ \(S\cap A=\emptyset\) _or_ \(N(C_{S}(A))\subseteq A\)_,_
3. _each cycle of_ \(CG(G)\) _has two edges that are of minimum weight among the edges of this cycle and are associated with the same set,_
4. _each cycle of_ \(CG(G)\) _has two edges that are of minimum weight among the edges of this cycle._  
Proof. : Let \(T\) be a clique tree of \(G\). \(1\Rightarrow 2\): let \(S\) be a minimal separator of \(G\) and let \(A\) be a maximal clique of \(G\) such that \(S\cap A\
eq\emptyset\). Let us show that \(N(C_{S}(A))\subseteq A\). Let \(XY\) be an edge of \(T\) associated with \(S\). As \(C_{S}(X)\
eq C_{S}(Y)\), at least one of them, say \(C_{S}(X)\) is different from \(C_{S}(A)\). Moreover, as \(S\subseteq X\) and \(S\cap A\
eq\emptyset\), it follows that \(X\cap A\
eq\emptyset\). Hence, \(XA\) is an edge of \(CG(G)\), i.e., of \(AG(G)\), so by item (a) of Lemma 3, \(N(C_{S}(A))\subseteq A\). \(2\Rightarrow 1\): as \(AG(G)\) is a subgraph of \(CG(G)\) with the same node set, it is sufficient to show that each edge of \(CG(G)\) is an edge of \(AG(G)\). Let \(XY\) be an edge of \(CG(G)\), and let us show that it is an edge of \(AG(G)\). Let \(Y^{\prime}\) be the neighbor of \(X\) on \(P_{T}(X,Y)\) and let \(S=X\cap Y^{\prime}\). As \(XY\) is an edge of \(CG(G)\) and \(X\cap Y\subseteq S\cap Y\), it follows that \(S\cap Y\
eq\emptyset\), and therefore \(N(C_{S}(Y))\subseteq Y\). As \(X\) and \(Y\) are in different connected components of \(T-\{XY^{\prime}\}\), \(C_{S}(X)\
eq C_{S}(Y)\)[15], so by item a) of Lemma 3 again \(XY\) is an edge of \(AG(G)\). \(1\Rightarrow 3\) immediately follows from Property 7. \(3\Rightarrow 4\) is evident. \(4\Rightarrow 1\): we assume for contradiction that \(AG(G)\
eq CG(G)\). Let \(XY\) be an edge of \(CG(G)\) that is not an edge of \(AG(G)\). Then, by Characterization 5 for each edge \(X^{\prime}Y^{\prime}\) of \(P_{T}(X,Y)\times Y\subset X^{\prime}\cap Y^{\prime}\). Hence, \(XY\) is the unique edge of minimum weight of the cycle of \(CG(G)\) formed by \(XY\) and \(P_{T}(X,Y)\), a contradiction. We immediately refind from Characterization 9 that a block graph has the same atom and clique graph since it satisfies item 2. If \(G\) is not chordal then its atom graph is necessarily different from its clique graph since its atoms are not its maximal cliques (a chordless cycle of length at least 4 is connected and has no clique separator, and therefore is a subset of some atom). However, Characterization 9 extends to each connected graph, replacing 'CG(G)' by 'the intersection graph of the set of atoms of \(G\)','minimal separator' by 'clique minimal separator' and'maximal clique' by 'atom' by Property 3. These classes are inclusion-uncomparable. The 3-sun is an atom graph (it is the atom graph of the graph shown in Figure 5). However, by Characterization 6 it is not a clique graph of a chordal graph (if it had a spanning tree \(T\) such that each maximal clique induces a subtree of \(T\) then each one of the three external triangles of the 3-sun would induce a subtree of \(T\), and therefore \(T\) would have a cycle).