the proof of unavoidable set of configuration

Question

I'm studying for the graph theory course and I don't understand the proof of the unavoidable set of configuration, especially, this one:

Wernicke showed that every cubic map that contains no triangle or quadrilater must contain 
two adjacent pentagons or a pentagon adjacent to a hexagon 
... and the configurations form an unavoidable set.

In order to prove this, we conducted the opposite case, where there are only 7 or more edged shapes (heptagons octagons...) neighboring the pentagons in the map, to derive a contradiction. The discharging method is used, and it states that:

(6-5)*C5+(6-6)*C6+(6-7)*C7+...=12

where the map has C5 pentagons, C6 hexagons, and so on.

This is where I'm stuck. I don't see how that equation leads to 12. The professor told us to use the Euler's formula, which is n-m+f=2, where n is number of vertices, m for edges, and f for faces. I've been trying to understand this for days and I almost gave up. So, my questions are:

1) how the heck did we get 12?

2) so how do I prove this theorem(?)?

Answer 1

Since there are $3$ edges incident to every vertex, we have $3n = 2m$. We can use this to eliminate $n$ from Euler's formula: $3n - 3m + 3f = 6$, so $3f - m = 6$. It will be convenient to double this, getting $6f - 2m = 12$.

If we sum the lengths of all faces, we get twice the number of edges, because each edge is counted twice (once from each side). That is, $$ \sum_{k=5}^\infty k \cdot C_k = 2m. $$ Substituting this into the formula $6f - 2m = 12$, we get $$ 12 = 6f - 2m = 6\left(\sum_{k=5}^\infty C_k\right) - \left(\sum_{k=5}^\infty k \cdot C_k\right) = \sum_{k=5}^\infty (6-k) C_k, $$ which proves the identity you wanted.

I can only guess at the specific discharging method used (in future, when asking questions about a proof, it's helpful to provide the entire proof!) but it's reasonable to begin by putting a charge of $6-k$ on each face of length $k$. Each pentagon now has charge $+1$, each hexagon charge $0$, and other faces have negative charge. The total charge is $12$.

Suppose, for the sake of contradiction, that pentagons are only adjacent to faces of length $7$ or more. In this case, do the following: for each pentagon, move $\frac15$ of its charge to each of the adjacent faces. What happens to the charge on each face?

• On any pentagon, we started at $+1$ charge, and lost $\frac15$ charge five times, so now we're at $0$.
• On any hexagon, we started at $0$, and didn't gain any charge (there were no adjacent pentagons), so we're still at $0$.
• On a face of length $k\ge 7$, we started at $6-k$ charge. We gained $\frac15$ charge at most $\frac k2$ times (since pentagons are never adjacent, at most $\frac k2$ of the faces bordering this one can be pentagons). So now we're at $6 - k + \frac{k}{10} = 6 - \frac{9}{10}k < 6 - \frac{9}{10}\cdot 7 = -\frac3{10}$ charge: we're definitely in the negatives.

As a result of this operation, we moved some charge around and now every face has charge at most $0$. Therefore the total charge is at most $0$ - but we started with a total charge of $+12$.

This is a contradiction, and so our assumption - that pentagons are only adjacent to faces of length $7$ or more - must be false. There must be some pentagons adjacent to faces of length $6$ or less: other pentagons, or hexagons.