## 4 Properties of \(\gamma\)-Graphs of Trees  
In this section, we investigate general properties of \(\gamma\)-graphs of trees. We begin with a result classifying the edges in \(\gamma\)-graphs of trees, highlighting the importance of cut edges and 4-cycles in these graphs. **Lemma 10**. : _Let \(T\) be a tree and let \(T(\gamma)\) be the \(\gamma\)-graph of \(T\). Every edge of \(T(\gamma)\) is a cut-edge or is contained in a 4-cycle._  
Proof. : Let \(e\) be an edge which is not a cut-edge of \(T(\gamma)\). Then \(e\) is contained in a cycle. But cycles in Algorithm 2 are only created at line 21, which always creates a 4-cycle. The result follows. We now show that a cut-edge, not incident with a leaf allows you to decompose a \(\gamma\)-graph of a tree into two smaller graphs, both of which are also \(\gamma\)-graphs of trees. **Lemma 11**. : _Let \(G\) be a \(\gamma\)-graph of a tree \(T\) with a cut-edge \(e\), and let \(G_{1}\) and \(G_{2}\) be the components of \(G\setminus e\). Then \(G_{1}+e\) and \(G_{2}+e\) are each \(\gamma\)-graphs of trees._  
Proof. : Let \(e=AB\) with \(A\in V(G_{1})\) and \(B\in V(G_{2})\) and assume \(A=(B-\{y\})\cup\{z\}\). Let \(\{z\}\cup\{z_{i}\}\) be the set of vertices that can be swapped from \(B\). Form \(T^{\prime}\) by adding a leaf to each \(z_{i}\). Since \(e\) is a cut-edge, \(z_{i}\) cannot be swapped in \(A\), and hence each \(z_{i}\) has exactly one external private neighbour in \(B\). But \(B\) is also a \(\gamma\)-set of \(T^{\prime}\), and each \(z_{i}\) has two external private neighbours. Moreover, each \(\gamma\)-set in \(G_{1}\) is also a \(\gamma\)-set of \(T^{\prime}\), so it follows that \(G_{1}+e\) is the \(\gamma\)-graph of \(T^{\prime}\). By symmetry, \(G_{2}+e\) is also the \(\gamma\)-graph of a tree. Setting \(G=H\) (see Figure 1) and \(e\) the edge joining the two stems of \(H\), shows the converse of Lemma 11 does not necessarily hold. That is both \(G_{1}+e=K_{1,3}\) and \(G_{2}+e=K_{1,3}\) are each \(\gamma\)-graphs of trees, but \(G=H\) is not a \(\gamma\)-graph of any tree. Lemma 11 does provide a tool for showing a graph with a cut-edge not incident to a leaf is not the \(\gamma\)-graph of any tree \(T\). For example, consider the graph \(Z\) shown in Figure 3. Let \(Z_{1}\) and \(Z_{2}\) be the components of \(Z\) obtained by deleting the edge \(e\), where \(Z_{2}\) is a tree. Then \(Z_{2}+e\) is a tree with adjacent vertices of degree at least 3 and thus by Theorem 10, \(Z_{2}+e\) is not the \(\gamma\)-graph of any tree \(T\). It now follows from Lemma 11 that \(Z\) is not the \(\gamma\)-graph of any tree \(T\). The remainder of the paper will focus on \(\gamma\)-graphs of trees where every edge is in a 4-cycle or incident with a leaf. We first present the following useful result due to [PERSON], [PERSON], and [PERSON] [3], which will be applied throughout. **Lemma 12**. : _[_3_]_ _For a \(\gamma\)-set \(D\) of a tree \(T\) and a vertex \(z\
otin D\), there is at most one vertex \(v\in D\) such that \((D-\{v\})\cup\{z\}\) is also a \(\gamma\)-set of \(T\)._  
We now demonstrate a key property of the \(\gamma\)-sets which when equated to their vertices form a 4-cycle of \(T(\gamma)\) that we will make extensive use of in our next set of results. **Proposition 2**. : _If \(G\) is a \(\gamma\)-graph of a tree \(T\) and \(WXYZ\) is a 4-cycle of \(G\), then for some distinct \(a,b\in W\) and distinct \(c,d\
otin W\) with \(a\sim c\) and \(b\sim d\), \(X=(W-\{a\})\cup\{c\}\), \(Z=(W-\{b\})\cup\{d\}\) and \(Y=(W-\{a,b\})\cup\{c,d\}=(Z-\{a\})\cup\{c\}=(X-\{b\})\cup\{d\}\)._  
Figure 3: The graph \(Z\). **Proof. ** For some \(p,r\in W\) and \(q,s\
otin W\) with \(p\sim q\) and \(r\sim s\) we have \(X=(W-\{p\})\cup\{q\}\) and \(Z=(W-\{r\})\cup\{s\}\). It follows from Lemma 12 that \(q\
eq s\). If \(q,s\
otin Y\), then as \(Y\
eq W\), for some vertex \(t\
otin X\cup Z\), with \(q,s\in N(t)\), \(Y=(X-\{q\})\cup\{t\}=(Z-\{s\})\cup\{t\}\) and \(p=r\) with \(p\
otin Y\). But then \(pqts\) is a 4-cycle in \(T\), which contradicts that \(T\) is a tree.