Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MATH 239
Due: Friday, November 25 at 10:00am A-8-1. {4 marks} Let G be a 4-regular connected graph with a planar embedding. Suppose that every face of the embedding has degree in {3, 5}. Let f5 be the number of faces of degree 5. Determine the number of faces of degree 3, call this f3, as a function of f5. Prove your assertions. A-8-2. {5 marks} The girth of a graphG is the length of the shortest cycle inG (where, by convention, the girth of G is∞ if G has no cycles). Prove that every planar graph with girth at least six has a vertex of degree at most two. A-8-3. {5 marks} A planar embedding of a graph G is called outerplanar if every vertex of G lies on the boundary of its outer face. A graph G is outerplanar if there exists an outerplanar embedding of G. Prove that if G is an outerplanar graph with n ≥ 2 vertices, then G has at most 2n− 3 edges. A-8-4. {6 marks} Use Kuratowski’s theorem to prove the following: Let G be a graph. (a) If G is not outerplanar, then G contains a subdivision ofK2,3 or a subdivision ofK4 as a subgraph. (b) If G contains a subdivision ofK2,3 or a subdivision ofK4 as a subgraph, then G is not outerplanar. For A-8-3 and A-8-4, you may assume the following theorem (without proof): Theorem 1. Let G be a graph and let G+ denote the graph obtained from G by adding a new vertex v and edges from v to all vertices of G. Then G+ is planar if and only if G is outerplanar.