4
$\begingroup$

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 Answers 1

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

  • 0
    Yes, it's necessary for the graph to be 2-connected. You may want to prove that fact just to be complete.2012-12-02