Problem 2:A tree is a finite connected nonempty (undirected) graph with no loops. (a): Suppose a spider moves from vertex to vertex of a finite tree G, never retracing its steps directly (i.e., by using the same edge twice in a row) but otherwise moving randomly. Show that the spider must get stuck at some point, and that it must be at a vertex of degree 1 when it gets stuck. Conclude that every tree has a vertex of degree 1. (b): Using part (a) and induction, show that a tree on n vertices has n - 1 edges. Figure 1: Two trees