Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations (Q1095812)

A traveling salesman cycle for a set S of sites in the Euclidean plane is a closed path of minimum total length that visits each site in S exactly once. A triangulation of S is a plane graph with the sites in S as its vertices and the sum of the lengths of all edges as its weight, and for which every region interior to the convex hull is a triangle. The Dulaunay triangulation of S, DT(S), is the graph whose vertices are the sites S with two sites \(s_ 1\) and \(s_ 2\) adjacent if \(V(s_ 1)\) and \(V(s_ 2)\) share a boundary consisting of more than one point, where V(s) is the set of points closer to s than to any other site. If no more than three V(s)'s meet at any point, DT(S) is said to be nondegenerate. By exhibiting an example, \(S=(4,6)\), (0,0), (5,0), (11,1,0.1), (9,2), (7,2), (6,10), this paper shows that DT(S) does not necessarily contain a traveling salesman cycle for S, even if DT(S) is nondegenerate and Hamiltonian, nor does a minimum weight triangulation.