Find the order and degree of the following recurrence relation. Also determine whether they are homogeneous or non-homogeneous.

<br><br> <img src='./qimages/9791-1a.jpg'> Solve the following recurrence relation using the characteristic equation: tn 6tn-1 9tn-2 for 1
to 0
t1= 1 Determine whether the following graphs are isomorphic. If yes, justify your answer.

<br><br> <img src='./qimages/9791-1c.jpg'>
What is an undirected graph? Prove that an undirected graph has even number vertices of odd degree.

2.(a) Define n-regular graph. Show for which value of n the following graphs are regular: Kn
Qn
What is a generating function? Find the generating function for the following sequence: 1 How many edges does a complete graph of 5 vertices have?

3.(a) Derive and explain a recursive relation expression for binary search algorithm.

(b) Define a graph and a subgraph. Show that for a subgraph H of a graph <img src='./qimages/9791-3b.jpg'>

4.(a) Define a bipartite graph. For which value of n is Qn bipartite
State and prove Euler's formula for a planar graph.
Show that a connected bipartite graph has a chromatic number of 2.

5.(a) State and prove Ore's theorem for a graph to be a Hamiltonian graph. What is a planar graph Determine whether the given graph is a planar. If so, redraw it such that no edges cross each other.

<br><br> <img src='./qimages/9791-5b.jpg'>