## 4 Theoretical Results
### Vertex Coloring  
In the following Lemma, we show the possible values for the chromatic number of a Delaunay graph.  
Lemma 2: _Let \(G\) be a Delaunay graph. Then, \(\chi(G)\) equals \(3\) or \(4\)._  
Proof: First, \(G\) is formed by triangles and the chromatic number of this type of graphs is three. Therefore it is obvious that \(\chi(G)\geq 3\). Moreover, \(G\) is a planar graph and, according to the well-known four-color theorem, it is satisfied that \(\chi(G)\leq 4\). Consequently, \(3\leq\chi(G)\leq 4\).  
Next, we give several results concerning sufficient conditions under which the chromatic number is three.  
Proposition 5: _Let \(G\) be a Delaunay graph. If \(G\) is Eulerian, then \(\chi(G)=3\)._  
Proof: Let \(G\) be a Delaunay Eulerian graph. According to Euler's Theorem, all the vertices of \(G\) have even degree. Let us denote by \(V\) the set of vertices of \(G\). Then, \(V\) can be decomposed as \(V=V^{\prime}\cup V^{\prime\prime}\), where \(V^{\prime}\) is the set of vertices of degree two and \(V^{\prime\prime}\) is the set of vertices with even degree greater or equal to four. Now, we show how to develop the vertex coloring of all the vertices in \(V^{\prime\prime}\). Notice that the vertices in this set are common vertices of at least three triangles. In this way, we start choosing one of these vertices and go through all its adjacent triangles, coloring the vertices alternatively and keeping the condition that there are no adjacent vertices with the same color. This is possible due to the fact that all the vertices have even degrees. In the case that there is a vertex with odd degree, we will not succeed in this procedure with only three colors. After this, we continue coloring the vertices from the set \(V^{\prime}\). Let us note that there are no pairs of vertices with degree two that are mutually adjacent, since in that case \(G\) would contain an internal face which is not a triangle. Due to this, every vertex in \(x\in V^{\prime}\) is adjacent to an internal triangle and can be colored according to the two colors already chosen for the other two vertices adjacent to \(x\).  
Proposition 6: _Let \(G\) be a Delaunay graph, which does not contain \(W_{n}\) with \(n\) being even as a subgraph. Then, \(\chi(G)=3\)._  
Proof: First, notice that \(G\) is a planar graph formed by triangles. Therefore, if \(G\) does not contain any wheel graphs with an even number of vertices as a subgraph, then \(G\) will not have any subgraphs with a chromatic number equaling four. This is due to the fact that the graphs made up of triangles whose chromatic number is equal to four contain as a  
Figure 6: Non-Hamiltonian Delaunay graph.  
subgraph the complete graph \(K_{4}\), which is isomorphic to \(W_{4}\), or a wheel graph with an even number of vertices.  
In order to obtain the 3-coloring of \(G\), it suffices to follow the method explained in Proposition 5.  
Corollary 1: _If all the vertices of a Delaunay graph, \(G\), belong to \(CH(G)\), then \(\chi(G)=3\)._  
Proof: Let \(G=(V,E)\) be a Delaunay graph such that \(V\subset CH(G)\). Then, \(G\) does not contain \(W_{n}\) as a subgraph \(\forall n\geq 4\). It follows from Proposition 6 that \(\chi(G)=3\).  
Corollary 2: _If a Delaunay graph, \(G\), verifies that \(1T(G)=\emptyset\), then \(\chi(G)=3\)._  
Proof: It follows from Corollary 1 and the fact that if \(G\) has no internal triangles, then all the vertices of \(G\) belong to \(CH(G)\).  
**Remark 1**: _Obviously the reciprocal of the previous corollary is not true. Moreover, the condition of having no internal triangles is not equivalent to the fact that all the vertices of \(G\) belong to the convex hull of \(G\). For example, the Delaunay graph of Figure 7 has one internal triangle and it is possible to obtain a 3-vertex coloring as indicated in that same figure._