## 1 Introduction
Finally, we will show GAMMATREE(\(T,c,S\)) obtains every edge of \(T(\gamma)\). We first demonstrate that the \(\gamma\)-sets are obtained by GAMMATREE(\(T,c,S\)) in order of depth. The algorithm GAMMATREE(\(T,c,S\)) can be implemented so that the \(\gamma\)-sets of \(T\) are obtained in order of depth. Proof. : Let \(D\) be a \(\gamma\)-set obtained by GAMMATREE(\(T,c,S\)). As GAMMATREE(\(T,c,S\)) runs, store the dominating sets of \(T\) (these are the elements of \(V\)) in a queue, so that first one discovered by GAMMATREE(\(T,c,S\)) is the first one processed by GAMMATREE(\(T,c,S\)). It suffices to prove that every \(\gamma\)-set \(D^{\prime}\) found from \(D\) (i.e., at line 14) is such that \(dp_{T}(D^{\prime})=dp_{T}(D)+1\). We observe that \(D^{\prime}=(D-\{v\})\cup\{x\}\) for adjacent vertices \(v\) and \(x\). If \(D=S\), then every \(z\in D-\{c\}\) has a child \(y\in pn(z,D)\), so \(x\) is a child of \(v\) and \(dp_{T}(D^{\prime})=dp_{T}(D)+1\) as desired. Now suppose \(D\
eq S\). If \(i(v)>i(D)\), then by Lemma 2, \(v\in S\) and every descendant of \(v\) which is in \(D\) is also in \(S\). It follows that \(v\) has a child \(y\in pn(v,D)\), so \(x\) must be a child of \(v\), and \(dp_{T}(D^{\prime})=dp_{T}(D)+1\) as desired. Otherwise, \(i(v)\leq i(D)\) and \(i(x)>i(D)\). Then it is clear that \(x\) is a child of \(v\), and the result again follows. Let \(T\) be a tree rooted at a vertex \(c\) and let \(S\) be the highest \(\gamma\)-set of \(T\). The algorithm GAMMATREE(\(T,c,S\)) can be implemented so that each edge in \(T(\gamma)\) is obtained by GAMMATREE(\(T,c,S\)). Proof. : Implement algorithm GAMMATREE(\(T,c,S\)) as required in Lemma 3 and suppose not all edges of \(\gamma(T)\) are obtained. Let \(D_{1}\) be the first \(\gamma\)-set found by GAMMATREE(\(T,c,S\)) such that there exists a \(\gamma\)-set \(D_{2}\), found before \(D_{1}\), where \(D_{2}=(D_{1}-\{z\})\cup\{y\}\), \(yz\in E(T)\), but edge \(D_{1}D_{2}\) is not obtained by GAMMATREE(\(T,c,S\)). By Lemma 3, \(dp_{T}(D_{2})=dp_{T}(D_{1})-1\). As \(D_{1}\) and \(D_{2}\) are both \(\gamma\)-sets of \(T\), we have \(pn(z,D_{1})=pn(y,D_{2})\subseteq\{y,z\}\). Suppose \(i(x)=i(D_{1})\). Then by Lemma 3, \(D_{1}\) was found while processing a set \(D_{3}=(D_{1}-\{x\})\cup\{w\}\), where \(w\) is the parent of \(x\) in \(T\). Clearly, neither nor \(D_{3}\) is \(S\). Hence, there exists a \(\gamma\)-set \(D_{4}\) such that \(D_{4}=(D_{3}-\{z\})\cup\{y\}=(D_{2}-\{x\})\cup\{w\}\). Moreover, since \(w\) is the parent of \(x\), we have  
\[dp_{T}(D_{4})+1=dp_{T}(D_{3})=dp_{T}(D_{2})=dp_{T}(D_{1})-1,\]  
so \(D_{4}\) is found before \(D_{2}\) and \(D_{3}\) by Lemma 3. Hence, \(D_{2}D_{4}\) and \(D_{3}D_{4}\) were both obtained by GAMMATREE\((T,c,S)\). In particular, \((D_{4},z)\in\mathrm{parents}(D_{3})\) and \((D_{2},x)\in\mathrm{children}(D_{4})\). Thus, we obtain the edge \(D_{1}D_{2}\) when processing \(D_{3}\), which is the contradiction proving the theorem. The correctness of the algorithm immediately follows. **Corollary 1**. : _Let \(T\) be a tree rooted at a vertex \(c\) and let \(S\) be the highest \(\gamma\)-set of \(T\). The algorithm GAMMATREE\((T,c,S)\) can be implemented to produce \(T(\gamma)\)._  
Proof. : By Theorem 6, we obtain every vertex of \(T(\gamma)\), and by Theorem 7, we obtain every edge of \(T(\gamma)\). The result follows.