8. Planar Graphs: (15 points) 2. A simple graph & has 9 vertices and 19 edges. If it 13 a planar sraph. how many faces must 1t have? b. Iz the following graph planar\" Explain. d. What is the maximum number of edges that a simple planar graph with 7 vertices may have? e. [ claim that the graph below iz planar. If T am right, draw this graph without any edges crossing. If T am wrong, explain why. Label the vertices: 2. Let connected graph G have vertex set '= (4, B, C; D, E, F} and the edge set as given below. In each situation, draw G with as few crossings as possible. (12 points) a) E1 = {(4, E); (A, F): (C, D); (B; D); (C. E); (B, F)} b) E1 = {(4, D); (A, C); (A, B); (A, E); (A, F); (B, E): (B, F); (C; D); (C; D): (D. F)} c) List the degrees of each vertex for each graph. Graph Fi: Graph E2: Degree( A) = Degree(A) = Degree (B) = Degree (B) = Degree (C) = Degree (C) = Degree(D) = Degree(D) = Degree (E) = Degree (E) = Degree (F) = Degree (F) = d) for each graph, list three pairs of adjacent vertices (if possible) and three pairs of non-adjacent vertices (if possible). If it is not possible, write "not possible". Graph El: Graph Er: Three pairs of adjacent vertices are: Three pairs of adjacent vertices are: Three pairs of non-adjacent vertices are: Three pairs of non-adjacent vertices are:3. For each pair of graphs, determine a) if they are equal; and b) if they aren't equal, then are they isomorphic? (6 points) a : 1 '-bG K o H e C J G| B G_-: V -{A.B,C,DrErF} l Ex ={{4, D}, {4, 3),(3.C}.{C. D}.{C, F}{D, E},{E, F}) 4. Which of the following graphs are bipartite? If they are, write out the two sets 4 and B that are bipartite. If they are not, explain why. (6 points) I