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.