The problem is in the title. Here is the hint given:
In the inductive case, try proof by contradiction. For this proof by contradiction, you may need to use the hand-shake lemma and concept of minimum degree. Show that the outcome of this proof contradicts the inductive hypothesis.
Not sure what it is meant by "concept of minimum degree" and how to apply the lemma. Any ideas?