[Solved] CSDS455 Homework 11

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