## 4 Properties of \(\gamma\)-Graphs of Trees
### Incident 4-Cycles in \(\gamma\)-Graphs of Trees
Hence, \(b\) and \(e\) have common neighbour \(j\) not adjacent to \(a=e\), a contradiction. Hence \(a\
eq e\). Similarly we can show \(b\
eq e\), \(a\
eq g\) and \(b\
eq g\). But then \(\mathit{aiejblgk}\) is a cycle in \(T\), contradicting that \(T\) is a tree. The result follows. Proposition 4: _Let \(G\) be a \(\gamma\)-graph of a tree \(T\) and let \(WXYZ\) and \(WVUS\) be 4-cycles of \(G\). Then there must be a 4-cycle \(WRQP\), with \(R\in\{X,Z\}\) and \(P\in\{S,V\}\)._  
Proof: Suppose not. Then neither \(S\) nor \(V\) is part of a 4-cycle with a pair vertices of \(WXYZ\). Hence, by Proposition 2 there are distinct vertices \(a,b\in W\) and \(c,d\
otin W\), with \(a\sim c\) and \(b\sim d\) so that \(S=(W-\{a\})\cup\{c\}\) and \(V=(W-\{b\})\cup\{d\}\). By Proposition 3, \(a=b\), a contradiction. The result follows. Define two 4-cycles of \(G\) to be _adjacent_ if they share an edge and two adjacent cycles to be neighbours. Then Proposition 4 can be reworded to say that incident 4-cycles in a \(\gamma\)-graph of a tree must be adjacent to each other or have a common neighbour. We conclude our treatment of vertices of 4-cycles by demonstrating that adjacent vertices of a 4-cycle cannot both have vertex neighbours that are not part of neighbouring 4-cycles. Proposition 5: _Let \(G\) be the \(\gamma\)-graph of a tree and let \(C\) be an induced \(C_{4}\) of \(G\). Then in any two adjacent vertices of \(C\) at most one has a neighbour which is not part of a 4-cycle with a pair of vertices of \(C\)._  
Proof: Suppose \(G\) is the \(\gamma\)-graph of a tree \(T\). Let \(C=WXYZ\) and suppose that \(W\) and \(X\) have neighbours \(U\) and \(V\) respectively, which are not part of a 4-cycle with any two vertices of \(C\). Recall a vertex of the \(\gamma\)-graph is a \(\gamma\)-set. By Proposition 2, there are distinct vertices \(a,b\in W\) and \(c,d\
otin W\) so that \(a\sim c\), \(b\sim d\), \(X=(W-\{a\})\cup\{c\}\), \(Z=(W-\{b\})\cup\{d\}\) and \(Y=(W-\{a,b\})\cup\{c,d\}\). There are vertices \(e\in W\), \(g\in X\), \(f\
otin W\) and \(h\
otin X\) so that \(e\sim f\), \(g\sim h\), \(U=(W-\{e\})\cup\{f\}\) and \(V=(X-\{g\})\cup\{h\}\). We note from Lemma 12 that \(d\), \(f\) and \(c\) are all distinct and that \(d\), \(h\) and \(a\) are all distinct. As neither \(U\) nor \(V\) is part of a 4-cycle with any two vertices of \(C\) we get:  
* if \(a\
eq e\), then as \((W-\{a,e\})\cup\{c,f\}\) is not a \(\gamma\)-set of \(T\), \(a\) and \(e\) have a common neighbour \(i\
otin N[b]\cup N[c]\). * if \(b\
eq e\), then as \((W-\{b,e\})\cup\{d,f\}\) is not a \(\gamma\)-set of \(T\), \(b\) and \(e\) have a common neighbour \(j\
otin N[a]\). * if \(b\
eq g\), then as \((X-\{b,g\})\cup\{d,h\}\) is not a \(\gamma\)-set of \(T\), \(b\) and \(g\) have a common neighbour \(k\
otin N[c]\). * if \(c\
eq g\), then as \((X-\{c,g\})\cup\{a,h\}\) is not a \(\gamma\)-set of \(T\), \(c\) and \(g\) have a common neighbour \(l\
otin N[a]\cup N[b]\). Note that in the case they exist, \(i\
otin\{j,k,l\}\) and \(k\
eq l\). If \(e\
otin\{a,b\}\) and \(g\
otin\{b,c\}\), then \(aclgkbjei\) is a cycle in \(T\), contradicting that \(T\) is a tree. Hence, by symmetry, we may assume either \(e=a\) or \(e=b\). Assume first that \(e=a\). Then as \(a\) and \(b\) are distinct, \(b\
eq e\). Therefore, from above \(a=e\) and \(b\) have a common neighbour \(j\). Since \(Y=(W-\{a,b\})\cup\{c,d\}\) is a \(\gamma\)-set of \(T\), it must be that \(j=c\) (if \(j\sim c\), then \(ajc\) is a 3-cycle in \(T\)). If \(b\
eq g\) and \(c\
eq g\), then as \(k\
eq c\), \(bclgk\) is a cycle in \(T\), which contradicts that \(T\) is a tree. If \(g=b\), as \(b\in W\) and \(c\
otin W\), \(c\
eq g\). From above \(c\) and \(g=b\) have a common neighbour, but \(c\) and \(b\) are adjacent, contradicting that \(T\) is a tree. If \(c=g\), then the path \(UWXV\) in \(G\) corresponds to a swap of \(f\) and \(a\), followed by a swap of \(a\) and \(c\), followed by a swap of \(c\) and \(h\).