1. Solving a recurrence relation [10 points] The function C(n) is dened with the following recurrence relation: 0 C(0)=1 0 C(11)= C(n-1) + 2 Using the technique shown in class, nd the closed form formula for C(n). 2. Euler and Hamiltonian cycles [20 points] Pictured below are the K313 and the K4,4 graphs. For each: a Does the graph have an Eulerian cycle? Explain why it does or does not. 0 Indicate a Hamiltonian cycle in each. Do this by listing the vertices in order in the cycle. For the K33, assume the top three vertices are labeled left to right a, b, and c and the three bottom are labeled left to right d, e, and f. For the K4)4 graph, assume the four left hand vertices are labeled from top to bottom a, b, c, and d and the four right hand vertices are labeled top to bottom e, f, g, and h