You will need to remove a vertex of degree one, apply the inductive hypothesis to the result, and then say which set the degree one vertex to.