Q$1$: Given an undirected graph $G=(V,E),$ and positive integer $k,$ the max$-$degree$-$spanning$-$tree

problem asks whether $G$ has a spanning tree whose degree is at most $k.$ The degree of a spanning

tree $T$ is defined as the maximum number of neighbors a node has within the tree $($i$.$e$.,$ a node

may have many edges incident on it in G$,$ but only some of them get included in T$).$ Show that

the max$-$degree$-$spanning$-$tree $($MDST$)$ problem is NP$-$complete. $(20$pts$)$