# Existence of optimal tours containing an 'extremal' edge

let $\mathcal{P}$ be a finite set of points in the euclidean plane in general position, and let $$\lbrace p_A,p_B,p_C,p_D\rbrace: \ \|p_C-p_A\|+\|p_D-p_B\|\ \gt \|p_i-p_h\|+\|p_k-p_j\|\quad\forall\ \mathcal{P}\supset\lbrace h,i,j,k\rbrace\ne\lbrace A,B,C,D\rbrace\subset\mathcal{P}$$ be the quadrilateral with the maximal induced maximum weight perfect matching.

Question:

Is it possible, that $\left( p_A,p_C\right)$ or $\left(p_B,p_D\right)$ is contained in the shortest tour through the points of $\mathcal{P}$?

I am convinced, that such a shortest tour can't exist, but don't know, how to go about proving that; therefore I am hoping for a proof proving or disproving the existence of such optimal tours.

• May you clarify? It is unclear whether (i) a route is supposed to be closed (=cyclic) or not, (ii) $\{\dots\}$ is a set or an ordered tuple, (iii) elements of $\{\dots\} may repeat or not... – Ilya Bogdanov Sep 15 '17 at 18:00 • Tours are round trips, where every city, resp. point is visited exactly once and the road, resp. edge, via which a city is entered, is different from the one via which it is left. So the sequence, in which the cities are visited, corresponds to a permutation with a single cycle. – Manfred Weis Sep 16 '17 at 6:57 • What about the other ambiguities? Do you thin that$\{A,D,B,C\}=\{A,B,C,D\}$or not? Do you allow$A=B$? – Ilya Bogdanov Sep 16 '17 at 8:39 • All points or cities shall be distinct, with a positive, finite real distance between each pair. – Manfred Weis Sep 16 '17 at 10:36 ## 1 Answer I assume that I interpret the question correctly (I fainled in getting a proper response...). In the left figure below you see a degenerate (almost-)counterexample: the tour$BACDEB$is the (unique) shortest one (because a tour cannot be shorter than the perimeter of$BDE$). The only trouble is that there are two pairs of edges (having no common vertices) with the maximal sum of lengths, namely$AC,BD$and$AD,BC$(all other distances are hopelessly shorter). This can be cured by modifying the picture a bit, replacing the line segment$BACD$by a thin parallelogram$ABCD\$, as shown in the right figure.

• Nice counter example! That helps me in the correct formulation of TSP heuristic. – Manfred Weis Sep 16 '17 at 15:49