## 4 Theoretical Results
### Hamiltonian  
The number of triangles, and more concretely the internal ones, is related to the existence of Hamiltonian cycles, as we show in the following results. Proposition 2: _If \(IT(DT(V))=\emptyset\), then \(DT(V)\) is Hamiltonian. Furthermore, either \(DT(V)\cong W_{n}\) or \(V\subseteq CH(V)\) (\(V=V(CH(V))\))._  
Proof. : First of all, we can assume that \(|V|=n>3\) since in case that \(|V|=3\) we would have a 3-cycle which is trivially Hamiltonian. Since \(n>3\), \(CH(V)\
eq DT(V)\), that is, \(DT(V)\) is not a 3-cycle. Now, we distinguish several cases. Case 1: \(\exists u\in V/u\
otin CH(V)\)  
Then, \(\forall v\in V\) with \(v\
eq u\), it is satisfied that \(v\in CH(V)\). This is due to the fact that if \(v\in V\) with \(v\
eq u\) verifies that \(v\
otin CH(V)\), then \(\exists w\in V/uvwu\) is a 3-cycle. Furthermore, \(uvwu\) is an internal triangle and \(IT(DT(V))=\emptyset\), but this is a contradiction. Therefore, there exists a unique \(u\in V-CH(DT(V))\), \(CH(V)\) has \(n-1\) vertices, and \(DT(V)\simeq C_{n-1}+K_{1}=W_{n}\). Therefore, \(DT(V)\) is Hamiltonian since every wheel graph is. Case 2: \(V\subseteq CH(V)\)  
Then, \(DT(V)\) is the cycle \(C_{n}\), where \(n\) is the total number of vertices in \(V\), adding some edges until creating the triangulation. Consequently, \(DT(V)\) is Hamiltonian and the Hamiltonian cycle is given by \(CH(V)\). Proposition 3: _If \(|IT(DT(V))|<3\), then \(DT(V)\) is Hamiltonian._  
Proof. : In the case that \(IT(DT(V))=\emptyset\), we know that \(DT(V)\) is Hamiltonian due to Proposition 2. Let us assume that \(DT(V)\) has one unique internal triangle, \(T\), whose vertices are \(\{u,v,w\}\). Since \(T\) is an internal triangle, each one of the edges \(uv\), \(uw\), and \(vw\) belongs to another 3-cycle. Now, we have two possibilities. On one hand, we suppose that there exist another three vertices \(\{a,b,c\}\) such that \(auv\), \(bvw\), and \(cuw\) determine the other three triangles containing the edges \(uv\), \(uw\), and \(vw\), respectively. In this case, those vertices \(\{a,b,c\}\) have degree two, \(|V|=6\) and \(V=V(CH(V))\). Consequently, \(CH(V)\) is the Hamiltonian cycle \(C_{6}\) and we conclude that \(DT(V)\) is Hamiltonian. On the other hand, if the previous situation is not satisfied, then \(V=\{u,v,w,a,b_{1},\ldots,b_{r}\}\), where \(a\) is the unique vertex with degree two. Moreover, \(a\) is adjacent to two vertices among \(\{u,v,w\}\). Without loss of generality, we can consider \(u\) and \(v\) to be those vertices. Then, \(w\) is the unique vertex which does not belong to \(CH(V)\) and the graph induced by \(V\setminus\{a\}\) is a wheel graph defined by \(C_{r+2}+w\). Every wheel graph is Hamiltonian and that Hamiltonian cycle can be extended considering also the edges \(au\) and \(av\). These two possible cases are represented in Figure 4.  
Now, we suppose that \(DT(V)\) has two internal triangles, \(T_{1}\) and \(T_{2}\). We have two possible cases since these two triangles can share a vertex or an edge. In the case that \(T_{1}\) and \(T_{2}\) have a common vertex, \(u\), they determine a friendship graph \(F_{2}\) and the remaining vertices of \(DT(V)\) belong to \(CH(V)\) since otherwise there would be more than two internal triangles. Following a similar reasoning as before with the wheel graph, it is possible to obtain a Hamiltonian cycle containing the vertices from \(CH(V)\) and \(u\). In the case that \(T_{1}\) and \(T_{2}\) share an edge, then both triangles are contained in a 4-cycle, \(C_{4}\). The Hamiltonian cycle of \(DT(V)\) is constructed by the union of \(C_{4}\) and \(CH(V)\). We show an example of both situations in Figure 5.  
In [9], the authors proved that a Delaunay graph always contains a Hamiltonian path when the distance considered is the square one (\(L^{\infty}\)-metric). It is an open problem if this is also true for the Euclidean distance. In the following proposition, we show that it is true that the previous statement is not true in case of Hamiltonian cycles.