Paragraph

  1. Find a Hamilton path. Can your path be extended to a Hamilton cycle?

  2. Is the graph bipartite? If so, how many vertices are in each “part”?

  3. Use your answer to part (b) to prove that the graph has no Hamilton cycle.

  4. Suppose you have a bipartite graph \(G\) in which one part has at least two more vertices than the other. Prove that \(G\) does not have a Hamilton path.

in-context