Question 2.57

27. A Hamiltonian path in a graph is a tour of the vertices that visits each vertex once and only once and that starts and ends at different vertices.

  1. Draw an example of a graph that has no Hamiltonian path and where all the vertices are 3-valent.
  2. Draw a graph that has no Hamiltonian path but that does have an Euler circuit.
  3. By analogy with the Hamiltonian path, develop a definition of “Euler path.”

71

27.

(a) Drawings will vary.

(b) Drawings will vary.

(c) Answers will vary.