Exercise 11.

Is there anything we can say about whether a graph has a Hamilton path based on the degrees of its vertices?

  1. Suppose a graph has a Hamilton path. What is the maximum number of vertices of degree one the graph can have? Explain why your answer is correct.

  2. Find a graph which does not have a Hamilton path even though no vertex has degree one. Explain why your example works.

in-context