Problems 1. Write an inductive proof of If _idi = 2(n-1), where di, d2, , dn are positive integers, then there is a tree with n vertices in which degree(vi) = di 2. What are you inducting on? What is the inductive variable? 3. State your inductive hypothesis as a function of your inductive variable . What is the BASE case? 5. Prove the BASE case 6. Carry out the INDUCTIVE STEP of the proof. This may involve some algebraic manipulation. 7. Use your inductive proof to design an algorithm for this construction problem. 8. Write and solve a difference equation for the running time of your algorithm