Let $K_n$ be a complete, undirected weighted graph. Starting from a vertex $v$ construct a greedy Hamiltonian path $P$ by always selecting the cheapest edge leading to a yet uncovered vertex. Starting from a vertex $u$ (which may be equal to $v$ or not) construct an anti-greedy Hamiltonian path $Q$ by always selecting the most expensive edge leading to a yet uncovered vertex. We show that the total weight of $P$ is at most the total weight of $Q$.
Without loss of generality we may assume that all weights are positive reals. For a set of edges $F$ and a real $x$ let $f(x, F)$ denote the number of edges in $F$ whose weight is at least $x$. It is easy to see that the total weight of the edges in $F$ is exactly$$\int_0^\infty f(x, F)\,dx.$$Thus, in order to prove the desired result it suffices to show that for any fixed $x$,$$f(x, P) \le f(x, Q).$$We proceed with a proof of that. Let $P(x)$ denote the set of all edges of $P$ whose weight is at least $x$. Then $P(x)$ is a union of connected components, and each of them is a path. Let$$C = c_1c_2 \ldots c_k$$be such a path that forms a component with at least one edge, thus$$|C| = k \ge 2.$$Assume that $C$ was selected greedily in this order, from $c_1$ to $c_k$. Note that the weight of every edge $c_ic_j$ with $1 \le i < j \le k$ is at least $x$. Indeed, this weight is at least the weight of $c_ic_{i + 1}$, as $P$ was chosen greedily. Consider now the path $Q$ chosen anti-greedily. As $Q$ is a Hamiltonian path all the vertices of $C$ appear in $Q$ in some order. We claim that for every $i$, $1 \le i < k$, the edge of $Q$ emanating from the vertex of $C$ that appears in place number $i$ in this order is of weight at least $x$. Indeed, when we chose this edge anti-greedily, there was still at least one yet uncovered vertex of $C$ and by the argument above the weight of the edge leading to it is at least $x$. Thus the weight of the edge chosen was at least $x$. This means that among the edges emanating from vertices of $C$ at least $k - 1$ have weight at least $x$, and as $C$ has $k - 1$ edges, summing over all components implies that indeed$$f(x, Q) \ge f(x, P),$$completing the proof.
