Using induction, show that

Tn where n 1,

where Tn =2Tn-1 1.
Prove that the complement of G is G. Draw at least 3 non-isomorphic graphs on 4 vertices. Prove that an= 3n/2-2 is a solution to the recurrence an 2an/2 where n is a power of 2 and a2=1.

2.(a) Find the number of bijections on a set of n elements, where n 1.
Consider the graph on 5 vertices and 7 edges given in the figure. Find xl to x5 walks of length 8 and length 4 respectively. <img src='./qimages/9281-2b.jpg'>

3.(a) If G is a graph with n vertices and k components, then prove that G can have at least n edges and at most ­k edges.
Solve the third order recurrence

Un -9Un-1 26Un-2-24Un-3=0,

where n with the initial conditions U0 Ul 17 and U2 =53.

4.(a) Solve the recurrence dk=k dk-1 if with d1 =0.
Find where G is the Petersen graph.

5.(a) Draw three spanning trees of the following graph: <img src='./qimages/9281-5a.jpg'>
What is the difference between an Eulerian graph and an Eulerian circuit?
Construct a graph with chromatic number5.
Solve the recurrence relation an an/2 1 for n 2^k where k a1 O.