Given an undirected graph G = (V, E). Find a spanning tree of G with the maximum number of vertices that have degree 1. Show that this problem is NP-complete.
For the NP-Complete proof, do the following ALSO:
1)Show clearly the decision version of the problem.
2)Show clearly the problem and instance that you want to reduce from.
3)Show clearly both the forward/reverse directions of the equivalence of your two instances