EECS 455: Applied Graph Theory
Homework 11
Problem 1: Let G be a simple, planar graph. Give each vertex v a “charge” of d(v) − 4 where d(v) is the
degree. Give each face f a “charge” of |f| − 4 where |f| is the number of vertices on the face. Prove that
the total charge of the graph is negative.
Problem 2: Let G be a simple, planar graph with δ(G) ≥ 3. Give each vertex v a “charge” of d(v) − 4,
and give each face f a “charge” of |f| − 4. Prove that if every vertex of degree 3 is adjacent to three faces
of size 6 or larger, then we can “discharge” the degree 3 vertices by transfering the negative charge of the
degree 3 vertices its adjacent faces such that every vertex of G and every face of G of size 6 or larger has
non-negative charge and such that the total charge of G does not change.
Problem 3: Prove that for any simple, planar graph G with δ(G) ≥ 3, there exists a vertex v on face f
such that d(v) + |f| ≤ 8. (Assume there is no such vertex or face and give a discharging rule that results in
every vertex and face of G having non-negative charge.)
