**Problem 1I: Let **.** Let **** be a graph with the elements of **** as vertices and an edge between **** and **** if and only if ** **for exactly one value of **** . Show that **** is Hamiltonian.**

**Solution**: When , the graph is trivial. Suppose . When , the graph is Hamiltionian since it is a complete graph. Assume that the graph is Hamiltonian for . Suppose a Hamiltonain circuit of the graph with vertices is . Then if is even, a Hamiltonian circuit for would be

If is odd, if use the same procedure, we would obtain

which cannot be a circuit. So we use a different procedure, keep the first points same as before, and the last points are:

This is a Hamiltonian circuit for odd The induction completes.

**Notes: **If is , we can find another way to produce Hamiltonian circuit by exchanging the points in the circuit of even case: W.L.O.G., assume there is a path segment from the Hamiltonian circuit of , and these points differ on the same position. Hence exchanging or exchanging would not destroy the Hamiltonian circuit. Now exchange , , and exchange , , then a Hamiltonian circuit forms.

Find a Hamiltonian circuit is not easy. In general case, it is NP hard. However, if the graph has a ‘nice’ representation, it might be easy to find one.