91Ó°ÊÓ

Suppose you have a supercomputer that can generate one billion \(\left(10^{9}\right)\) Hamilton circuits per second.(a) Estimate (in years) how long it would take the supercomputer to generate all the Hamilton circuits in \(K_{21} .\) (Hint: There are about \(3.15 \times 10^{7}\) seconds in a year.) (b) Estimate (in years) how long it would take the supercomputer to generate all the Hamilton circuits in \(K_{22} .\) (Hint: There are about \(3.15 \times 10^{7}\) seconds in a year.)

(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 ?\)

(a) How many edges are there in \(K_{200}\) ? (b) How many edges are there in \(K_{201}\) ? (c) If the number of edges in \(K_{500}\) is \(x\) and the number of edges in \(K_{501}\) is \(y,\) what is the value of \(y-x ?\)

In each case, find the value of \(N\). (a) \(K_{N}\) has 720 distinct Hamilton circuits. (b) \(K_{N}\) has 66 edges. (c) \(K_{N}\) has 80,200 edges.

A complete bipartite graph is a graph with the property that the vertices can be divided into two sets \(A\) and \(B\) and each vertex in set \(A\) is adjacent to each of the vertices in set \(B\). There are no other edges! If there are \(m\) vertices in set \(A\) and \(n\) vertices in set \(B,\) the complete bipartite graph is written as \(K_{m, n} .\) Figure \(6-52\) shows a generic bipartite graph. (a) For \(n>1\), the complete bipartite graphs of the form \(K_{n, n}\) all have Hamilton circuits. Explain why. (b) If the difference between \(m\) and \(n\) is exactly 1 (i.e., \(|m-n|=1\) ), the complete bipartite graph \(K_{m, n}\) has a Hamilton path. Explain why. (c) When the difference between \(m\) and \(n\) is more than 1 , then the complete bipartite graph \(K_{m, n}\) has neither a Hamilton circuit nor a Hamilton path. Explain why.

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.