# Properties and Recognition of Atom Graphs
## 6 Atom Graph and Union Join Graph
Hence, according to Characterization 13 below, trees and complete graphs are atom graphs, which also follows from Characterization 14. **Characterization 13**. : _A connected graph is an atom graph if and only if it is an AG-expanded tree._  
To prove Characterization 13, we will use the following Lemma. **Lemma 4**. : _Let \(T\) be a join tree of a connected hypergraph, let \(X\), \(Y\) be distinct nodes of \(T\) and let \(X_{m}Y_{m}\) be an edge of \(P_{T}(X,Y)\) whose associated set is inclusion-minimal among the sets associated with the edges of \(P_{T}(X,Y)\). Then, \(XY\) is an edge of \(tuj(T)\) if and only if \(X\cap Y=X_{m}\cap Y_{m}\) (or equivalently \(X_{m}\cap Y_{m}\subseteq X\cap Y\))._  
Proof. : We assume that \(XY\) is an edge of \(tuj(T)\). Let \(X^{\prime}Y^{\prime}\) be an edge of \(P_{T}(X,Y)\) such that \(X\cap Y=X^{\prime}\cap Y^{\prime}\). As \(X\cap Y\subseteq X_{m}\cap Y_{m}\) and \(X\cap Y=X^{\prime}\cap Y^{\prime}\
ot\subset X_{m}\cap Y_{m}\), \(X\cap Y=X_{m}\cap Y_{m}\). The converse implication is evident  
Proof. : (of Characterization 13) By Characterization 10 it is sufficient to show that there is a join tree \(T\) of a connected \(\alpha\)-acyclic hypergraph such that \(G\) is isomorphic to \(tuj(T)\) if and only if \(G\) is an AG-expanded tree. \(\Rightarrow\): let \(T\) be a join tree of a connected hypergraph such that \(G\) is isomorphic to \(tuj(T)\). It is sufficient to show that \(tuj(T)\) is an AG-expanded tree. Let \(S_{e}=(e_{1}=X_{1}Y_{1},\ldots,e_{p}=X_{p}Y_{p})\) be an ordering of the edges of \(T\) ordered by increasing weight, and let \(S_{V}=(V_{1},\ldots,V_{p})\) where \(V_{i}\) is the connected component of \(T(\mathcal{E}_{S_{i}})-\{e_{j},\ 1\leq j<i\}\) containing \(e_{i}\), \(\mathcal{E}_{S_{i}}\) being the set of nodes of \(T\) containing \(S_{i}=X_{i}\cap Y_{i}\), for each \(i\in[1,p]\). Let us show that \((T,S_{e},S_{V})\) is an AG-structure of \(tuj(T)\). \(T\) is a spanning tree of \(tuj(T)\). Let \(i,j\in[1,p]\). By definition of \(V_{i}\), \(T(V_{i})\) is a subtree of \(T\) containing the edge \(e_{i}\) and if \(e_{j}\) is an edge of \(T(V_{i})\) then \(j\geq i\) and \(V_{j}\subseteq V_{i}\) (as \(e_{j}\subseteq V_{i}\), \(S_{i}\subseteq X_{j}\cap Y_{j}=S_{j}\)). Let \(\{X,Y\}\) be a pair of nodes of \(T\), and let \(i=min\{j\in[1,p]\), \(e_{j}\) is an edge of \(P_{T}(X,Y)\}\). Let us show that \(XY\) is an edge of \(tuj(T)\) if and only if \(\{X,Y\}\subseteq V_{i}\). By Lemma 4 and the definition of \(i\), \(XY\) is an edge of \(tuj(T)\) if and only if\(S_{i}\subseteq X\cap Y\), which is still equivalent to \(\{X,Y\}\subseteq V_{i}\) since \(T(\mathcal{E}_{S_{i}})\) is connected and for each edge \(e_{j}\) of \(P_{T}(X,Y)\), \(j\geq i\). Hence, \((T,S_{e},S_{v})\) is an AG-structure of \(tuj(T)\), which implies that \(tuj(T)\) it is an AG-expanded tree. \(\Leftarrow\): let \(G=(V,E)\) and let \((T,S_{e},S_{V})\) be an AG-structure of \(G\), with \(S_{e}=(e_{1}=x_{1}y_{1},\ldots,e_{p}=x_{p}y_{p})\) and \(S_{V}=(V_{1},\ldots,V_{p})\). Let \(H\) be the hypergraph \((V^{\prime},\mathcal{E})\) where \(V^{\prime}=V+\{v_{1},\ldots,v_{p}\}\) and \(\mathcal{E}=\{A_{x},\ x\in V\}\), with \(A_{x}=\{x\}+\{v_{i},\ i\in[1,p]\wedge x\in V_{i}\}\). Let \(f\) map each vertex \(x\) of \(G\) to the hyperedge \(A_{x}\) of \(H\), and let \(T^{\prime}=f(T)\). As \(T(V_{i})\) is a subtree of \(T\) for each \(i\in[1,p]\), \(T^{\prime}\) is a join tree of \(H\), and as no edge of \(T^{\prime}\) is associated with  
Figure 6: An AG-expanded tree \(G\) and one of its AG-expanded structures. the empty set (the set associated with \(f(e_{i})\) contains at least \(v_{i}\) since \(e_{i}\) is an edge of \(T(V_{i})\)), \(H\) is connected. Let us show that \(G\) is isomorphic to \(tuj(T^{\prime})\). Let \(\{x,y\}\subseteq V\). Let us show that \(xy\) is an edge of \(G\) if and only if \(A_{x}A_{y}\) is an edge of \(tuj(T^{\prime})\). Let \(i=min\{j\in[1,p]\), \(e_{j}\) is an edge of \(P_{T}(x,y)\}\).