If for a complete graph (or one with very few edges missing), our data is an n × n distance table (as in Prob. 13), show that the present algorithm [which is O(n²)] cannot easily be replaced by an algorithm of order less than O(n²).

Data from Prob. 13

Find a shortest spanning tree in the complete graph of all possible 15 connections between the six cities given (distances by airplane, in miles, rounded). Can you think of a practical application of the result?

Denver Los Angeles Dallas New York Washington, DC 900 1800 1300 850 650 1200 1500 2350 200 Chicago 800 700 1350 Dallas 650 1650 2500 Denver Los Angeles New York