Problem $8\mathrm{.}12($a$,$b$).$ The k$-$spanning tree problem is as follows:

Input: An undirected graph G $=($V$,$ E$).$

Output: A spanning tree of G in which each node has degree $<=$ k$,$ if such a tree

exists.

Show that for any k $>=2$:

$($a$)$ k$-$spanning tree is a search problem.

$($b$)$ k$-$spanning tree is NP$-$complete. $($Hint: Start with k $=2$ and consider the relation

between this problem and Rudrata path.$)$