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

I'm confused about how to go about this. Some properties that could be relevant are:

  • 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?


1 Answer 1


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

  • $\begingroup$ thank you! the trick here was to see that there are deg(v) faces incident with each vertex. I'm assuming thats because the graph is 2-connected? $\endgroup$
    – DustinH
    Dec 2, 2012 at 15:53
  • $\begingroup$ Yes, it's necessary for the graph to be 2-connected. You may want to prove that fact just to be complete. $\endgroup$
    – EuYu
    Dec 2, 2012 at 18:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .