(a) Find chromatic number of bipartite graph Km, n. 
(b) Is every subgraph of a regular graph regular ? Justify. 
(c) Construct a 5-regular graph on 10 vertices.

Is a Hamiltonian graph Eulerian ? Is a Eulerian graph Hamiltonian ? Show with the help of a suitable example.

Define a recurrence relation. Describe the following problems with the help of examples which can be solved through Divide and Conquer technique and Show its recurrence relation.
(i) Binary Search
(ii) Merge Sort
Solve these recurrence relations with a substitution method

Verify, “If an undirected graph has exactly two vertices of odd degree there must be a path joining these two vertices.”

a) Find a recurrence relation and initial conditions for 4,14,44,134, 404, …
b) Find the generating function of 2, 4, 8, 16, 32, ...

(a) Find chromatic number of bipartite graph Km, n. 
(b) Is every subgraph of a regular graph regular ? Justify. 
(c) Construct a 5-regular graph on 10 vertices.

Define homogeneous recurrence relation. Write the first order and second order homogeneous recurrence relations with constant coefficients giving an example for each. Solve the following recurrence relation:  for  given that