代写MATH 239、代写C++，Java程序

日期：2022-11-23 08:14

MATH 239 Fall 2022

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.