Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

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

share|improve this answer
    
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? –  DustinH Dec 2 '12 at 15:53
    
Yes, it's necessary for the graph to be 2-connected. You may want to prove that fact just to be complete. –  EuYu Dec 2 '12 at 18:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.