91Ó°ÊÓ

(a) How many edges are there in \(K_{20}\) ? (b) How many edges are there in \(K_{21}\) ? (c) If the number of edges in \(K_{50}\) is \(x\) and the number of edges in \(K_{51}\) is \(y,\) what is the value of \(y-x ?\)

In each case, find the value of \(N\). (a) \(K_{N}\) has 120 distinct Hamilton circuits. (b) \(K_{N}\) has 45 edges. (c) \(K_{N}\) has 20,100 edges.

Suppose that in solving a TSP you use the nearest-neighbor algorithm and find a nearest-neighbor tour with a total length of 21,400 miles. Suppose that you later find out that the length of an optimal tour is 20,100 miles. What was the relative error of your nearest-neighbor tour? Express your answer as a percentage, rounded to the nearest tenth of a percent.

(a) Explain why a graph that has a bridge cannot have a Hamilton circuit. (b) Give an example of a graph with bridges that has a Hamilton path.

If \(G\) is a connected graph with \(N\) vertices and \(\operatorname{deg}(X) \geq \frac{N}{2}\) for every vertex \(X,\) then \(G\) has a Hamilton circuit. Explain why Dirac's theorem is a direct consequence of Ore's theorem.