Q (a) K5 6. How many vertices and how many edges do each of the following graphs have? (b) CA (C) WS (d) K2,5 7. Does a simple graph that has five vertices each of degree 3 exist? If so, draw such a graph. If not, explain why no such graph exists. 8. How many nonisomorphic simple graphs are there with three vertices? Draw examples of each of these. 9. Is there an Euler circuit in the following graph? If so, find such a circuit. If not, explain why no such circuit exists. BA 10. Is there a Hamilton circuit in the graph shown in problem 4? If so, find such a circuit. If not, prove why no such circuit exists. 1 1. Is the following graph planar? If so draw it without any edges crossing. If it is not, prove that it is not planar. a 12. What is the chromatic number of each of the graphs in problem 6? Explain your answers. 13. Find a minimum spanning tree in the following weighted graph using Prim's algorithm. 4 2 3 C a 4 5 5 1 2 d e 1 3 3 7 h 5 414. What is the value of the Boolean function f (x, y, z) = (x + y)z + x y z when x = 1 , y = 0 and z = 1? 15. Prove or disprove that x y + y = y whenever x and y are Boolean variables. 16. Prove or disprove that x + xy + xyz = x whenever x, y, and z are Boolean variables. 17. Construct a finite-state machine that models a vending machine accepting only quarters that gives a container of orange juice when 50 cents has been deposited, followed by a button being pushed. The possible inputs are quarters and the button, and the possible outputs are nothing, orange juice, and a quarter. The machine returns any extra quarters.) 18. Suppose that A = {1, 11, 01} and B = {0, 10}. Find AB and BA. 19.Let A = {1, 10}. Which strings belong to A*? 20. What is the output produced by the following finite-state automaton when the input string is Bore 11101? 1, 1 your a start So S1 ers Which of them relat 0, 0 Which of these relations are we . Slugs that the relation R = [(x ) 1 x - 1, 0 1, 0 alonce relation on the dontive What are the equivalence 5, Consider the poses with the following Hasso $2Review Problems for the Final Exam Math 285 Spring 2024 1. Let f(n) = 3n? + 8n + 7 . Show that f (n) is O(n?). Be sure to specify the values of the witnesses C and k. 2. Show that the function f{x) = (x+ 2)log(>& + 1) + log(x3 + 1) is O(xlog X). 3. Consider the following relations on the set of positive integers. Ri={(xy)| x+y > 10} IR =1i(5c y) | Yy divides x} R; ={(x, Y) | ged(x y)=1} R, ={ (% y) | xand y have the same prime divisors } Which of these relations are reflexive? Justify your answers. Which of these relations are symmetric? Justify your answers. Which of these relations are antisymmetric? Justify your answers. Which of these relations are transitive? Justify your answers. 4. Show that the relation R = {(x, y) | x y is an integer} is an equivalence relation on the set of rational numbers. What are the equivalence classes of 0 and ! ? 2 5. Consider the poset with the following Hasse diagram. | AN Rl Find all maximal elements of the poset. Find all minimal elements of the poset. Find the least element of the poset if it exists, or show that it does not exist. Find the greatest element of the poset if it exists, or show that it does not exist k What is the greatest lower bound of the set {a, b, c}? What is the least upper bound of the set {a, b, c}