Discrete Mathematics Questions. Please do read the questions carefully.

2. (a) Determine whether or not f(x) = x4/3 is O(x2) . Justify your an- swers mathematically (b) Show that x log x is O(x2) but that x2 is not O(x log x) (c) Give as good a big-O estimate for each of these functions below (i) (nlogn + n2) (n3 + 4) (ii) (n! + 2") (n+ + log(n2 + 1)) .3. (a) (i) Draw a graph with four vertices of degrees 1, 2, 3, and 4 respec- tively. (ii) Draw a simple graph that has four vertices with degrees 1, 2, 2, and 3. (iii) Draw two non-isomorphic graphs with two vertices of same de- gree sequence. (v) Draw two examples of bipartite graphs, one that is complete and one that is not. (b) Draw all possible 5-vertex trees with maximum degree 3.1. (i) Consider the power set 'P(X). Let X : {1. 2.3}. Draw the Hasse Diagram for 73(X) .~ (ii) Consider the relation R on the set A : {0. 1. 2. 3. 4} given by R = {,,,311,}. (a) Draw the directed graph of R. u (b) Find all the equivalence classes of R. (iii) Let B : {1.2.3.4} and consider the relation R dened on B as follows; R : {(1. 2). (2. 3). (3. 4)} . Find the transitive closure of R