Exercise $10\mathrm{.}4\mathrm{.}5$ : A Hamilton path in a graph $G$ is an ordering of all the nodes

$n_1,n_2,$dots,$n_k$ such that there is an edge from $n_i$ to $n_{i+1},$ for all $i=1,2,$dots,$k-1.$

A directed Hamilton path is the same for a directed graph; there must be an arc

from each $n_i$ to $n_{i+1}.$ Notice that the Hamilton path requirement is just slightly

weaker than the Hamilton$-$circuit condition. If we also required an edge or arc

from $n_k$ to $n_1,$ then it would be exactly the Hamilton$-$circuit condition. The

$($directed$)$ Hamilton$-$path problem is: given a $($directed$)$ graph, does it have at

least one $($directed$)$ Hamilton path?

a$)$ Prove that the directed Hamilton$-$path problem is NP$-$complete. Hint:

Perform a reduction from DHC$.$ Pick any node, and split it into two, such

that these two nodes must be the endpoints of a directed Hamilton path,

and such a path exists if and only if the original graph has a directed

Hamilton circuit.

b$)$ Show that the $($undirected$)$ Hamilton$-$path problem is NP$-$complete. Hint:

Adapt the construction of Theorem $10\mathrm{.}23.$

$*!$ c$)$ Show that the following problem is NP$-$complete: given a graph $G$ and

an integer $k,$ does $G$ have a spanning tree with at most $k$ leaf vertices?

Hint: Perform a reduction from the Hamilton$-$path problem.

$!$ d$)$ Show that the following problem is NP$-$complete: given a graph $G$ and

an integer $d,$ does $G$ have a spanning tree with no node of degree greater

than $d?($The degree of a node $n$ in the spanning tree is the number of

edges of the tree that have $n$ as an end.$)$