# 2-connected planar graph and vertex degree

If $G$ is a 2-connected loopless planar graph, and for each vertex $v$ we define: $f(v) = (1/2) - (1/deg(v))$, where $deg(v)$ is the degree of vertex $v$,

Show that for some region $R: \sum f(v) < 1$, where the sum is over all vertices $v$ incident with $R$.

• for 2-connected planar graphs, every region is bounded by a cycle
• $12 \leq \sum [6 - deg(v)]$ so $\sum deg(v) \leq 6|V(G)| - 12$
• $\sum deg(v) = 2 |E(G)|$
• every region is clearly bounded by at least 3 edges and thus has at least 3 vertices incident to it
• for 2-connected graphs, every vertex has $deg(v) \geq 2$

Anyone have ideas?

-

Let us denote the sum for a region as $$F(R) = \sum_{v\in R}f(v)$$ Consider the sum of $F$ over all regions of the graph. There are $\deg v$ faces incident with each vertex so each $f(v)$ is counted precisely $\deg v$ times. $$\sum_{R\in G}F(R) = \sum_{v\in G} f(v)\deg v=\sum_{v\in G}\left(\frac{\deg v}{2}-1\right)$$ From the handshaking lemma, this is equal to $$\sum_{R\in G}F(R)=|E| - |V|$$ From Euler's formula $$|E|-|V| = |R|-2$$ where $|R|$ is the number of regions. Therefore the average of $F$ over the regions $$\overline{F(R)} = \frac{|R|-2}{|R|}<1$$ is less than $1$. Therefore there must exist at least one region for which $F(R)$ itself is less than $1$.