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.)