The celebrated theorem of Beardwood, Halton and Hammersley gives that the shortest TSP tour through n random points in the unit square is asymptotically $\beta\sqrt{n}$, for some constant $\beta$. Similar asymptotic formulas for random point-sets are known to hold for other quantities; i.e., the minimum-length matching, shortest 2-factor, minimum spanning tree, etc. The constants $\beta$ in these formulas remain unknown, however, with only very weak rigorous bounds. We prove, at least, that the constants are different; that is, we prove that the TSP tour is asymptotically longer than the minimum spanning tree, than the minimum 2-factor, than twice a matching, etc. We will also asymptotically separate the TSP from its linear programming relaxation. As a consequence, we learn that a natural class of algorithms which is often employed in practice cannot hope to solve even random instances of the Euclidean TSP efficiently.