(a) Let G be a graph in which there are no vertices of degree 1. Prove that G contains a cycle with at most 2dlg ne vertices of degree 3 or more, and it can be found in linear time. (b) Show that the claim is not true if degree 1 vertices are allowed in the graph.