## 4 Properties of \(\gamma\)-Graphs of Trees
### Incident 4-Cycles in \(\gamma\)-Graphs of Trees  
In this subsection we give some structure to how four cycles interact locally in \(\gamma\)-graphs of a trees. We first demonstrate that \(K_{2,3}\) cannot be a subgraph of a \(\gamma\)-graph of a tree. As a consequence, we observe that two 4-cycles have at most two common vertices, and moreover, if two 4-cycles have two common vertices, then the two common vertices are adjacent. Theorem 13: _Let \(T\) be a tree and let \(T(\gamma)\) be the \(\gamma\)-graph of \(T\). Then \(T(\gamma)\) does not contain \(K_{2,3}\) as a subgraph._  
**Proof. ** For \(i\in\{1,2,3\}\) and \(j\in\{1,2\}\) let \(Y_{i}\) and \(X_{j}\) be vertices of \(T(\gamma)\) that induce \(K_{2,3}\). That is \(X_{j}\sim Y_{i}\) for each possible \(i\) and \(j\). Then for each \(i\in\{1,2,3\}\) there exist vertices \(a_{i}\in X_{1}\) and \(b_{i}\
otin X_{1}\) with \(a_{i}\sim b_{i}\) and \(Y_{i}=(X_{1}-\{a_{i}\})\cup\{b_{i}\}\). By Lemma 12, it must be the case that \(b_{1}\), \(b_{2}\) and \(b_{3}\) are all distinct. It follows from Theorem 3 that \(X_{1}\) and \(X_{2}\) are at distance two in \(T(\gamma)\). Therefore \(|X_{2}\setminus X_{1}|\leq 2\) and so for some \(i\), \(b_{i}\
otin X_{2}\setminus X_{1}\). Assume with out loss of generality \(b_{3}\
otin X_{2}\setminus X_{1}\). As \(b_{3}\
otin X_{1}\) it must be the case that \(b_{3}\
otin X_{2}\). Then for some vertex \(c\
otin Y_{3}\) with \(c\sim b_{3}\), \(X_{2}=(Y_{3}-\{b_{3}\})\cup\{c\}\), and it follows that \(X_{2}=(X_{1}-\{a_{3}\})\cup\{c\}\) and therefore \(a_{3}\
eq c\). As each \(b_{i}\) is distinct, we can assume without loss of generality that \(b_{2}\
eq c\). Then \(X_{2}=(Y_{2}-\{a_{3},b_{2}\})\cup\{a_{2},c\}\). But \(d(X_{2},Y_{2})=1\), so \(|X_{2}\setminus Y_{2}|=1\), which shows it must be the case that \(a_{2}=a_{3}\). Clearly \(b_{2}\) and \(b_{3}\) are both adjacent to \(a_{3}\) in \(T\). Furthermore \(X_{2}\) is adjacent to \(Y_{2}\) in \(G\) and \(X_{2}=(Y_{2}-\{b_{2}\})\cup\{c\}\) so it must be the case that \(b_{2}\) is adjacent to \(c\) in \(T\). By definition, \(c\sim b_{3}\) so either \(cb_{2}a_{3}b_{3}\) forms a cycle in \(T\) or \(c=a_{3}\). Both cases lead to a contradiction. \(\square\)  
We have shown that two 4-cycles in \(T(\gamma)\) cannot overlap in more than two vertices. On the other hand, we can also say something about the structure required in \(T(\gamma)\) when two 4-cycles have only one common vertex. We first establish the following. Proposition 3: _Let \(G\) be a \(\gamma\)-graph of a tree \(T\) and let \(C=WXYZ\) be a 4-cycle of \(G\). By Proposition 2 there are distinct \(a,b\in W\) and distinct \(c,d\
otin W\) with \(a\sim c\) and \(b\sim d\), so that \(X=(W-\{a\})\cup\{c\}\), \(Z=(W-\{b\})\cup\{d\}\) and \(Y=(W-\{a,b\})\cup\{c,d\}\). If \(U\) and \(V\) are each adjacent to \(W\) but not part of a 4-cycle with a pair of vertices of \(C\) and \(U=(W-\{e\})\cup\{f\}\) and \(V=(W-\{g\})\cup\{h\}\), then \(e=g\)._  
**Proof. ** Suppose the opposite. It follows from Lemma 12 that \(c\), \(d\), \(f\) and \(h\) are all distinct. As neither \(U\) nor \(V\) is part of a 4-cycle with any two vertices of \(C\), \((W-\{a,e\})\cup\{c,f\}\) is not a \(\gamma\)-set of \(T\). Hence, if \(a\
eq e,a\) and \(e\) have common neighbour \(i\) which is not adjacent to any vertex in \((W-\{a,e\})\cup\{c,f\}\). As \(b\), \(g\in(W-\{a,e\})\cup\{c,f\}\), \(i\) is not adjacent to \(b\) or \(g\) in \(T\). Similarly it can be seen \((W-\{b,e\})\cup\{d,f\}\), \((W-\{a,g\})\cup\{c,h\}\), and \((W-\{b,g\})\cup\{d,h\}\) are not \(\gamma\)-sets of \(T\). Hence, if \(b\
eq e\), \(b\) and \(e\) have common neighbour \(j\) not adjacent to \(a\) or \(g\), if \(a\
eq g\), thenhave common neighbour \(k\) not adjacent to \(b\) or \(e\), and if \(b\
eq g\), \(b\) and \(g\) have common neighbour \(l\) not adjacent to \(a\) or \(e\). It can be seen that \(i,j,k,l\) (if they exist) are all distinct. Suppose \(a=e\). Then as \(a\) and \(b\) are distinct, \(b\
eq e\).