0

This is a corollary of Euler's formula. I know the proof for connected planar graphs but I have to prove it for unconnected planar graphs.

Suppose $G$ is a connected planar graph, with $v$ nodes, $e$ edges, and $f$ faces, where $v \geq 3$. Then prove that $e \leq 3v − 6$.

rlartiga
  • 4,205
  • 1
  • 14
  • 24
Giorgia
  • 7
  • What have you tried so far? Are you aware of any property of planar graphs, that would help you? – frabala Mar 25 '14 at 00:57
  • Hint: Apply the formula $e\leq 3v-6$ to each connected components of $G$. – Paul Mar 25 '14 at 01:29
  • @frabala I am trying to use Euler's Characteristic Theorem v - e + f = 2 but it also stands for connected graphs, so I thought about applying it to the connected components. I also can use another formula which I proved which is: e <= (v-2)c/(c-2) where every cycle in G has length at least c. – Giorgia Mar 25 '14 at 01:55

1 Answers1

0

For a connected planar graph

You know that the degree, $d(p)$ of each face $p$ of a planar graph is at least $3$. So, you have $$2e=\sum_{p}d(p)\geq \sum_{p}3=3f$$

But by Euler's formula, you have that $f=2+e-v$. By substituting this to the above inequality, you get \begin{align} 3(2+e-v)&\leq 2e\Leftrightarrow\\ 6+3e-3v&\leq 2e\Leftrightarrow\\ e&\leq 3v-6 \end{align}

For more than one connected components

Say the graph is not connected and it consists of $k$ connected components, each of which has $e_i$ number of edges, $v_i$ number of vertexes and $f_i$ number of faces, $i=1,\ldots,k$. Then, you get $e_i\leq 3v_i-6$ for each $i=1,\ldots,k$. By summing these inequalities, you get \begin{align} \sum_{i=1}^k e_i&\leq\sum_{i=1}^k \left(3v_i-6\right)\Leftrightarrow\\ e&\leq 3v-6k \end{align}

  • You can also check this relevant question from which you can get an even better result: $e\leq 3v-3k-3$.
  • And here is a question from which you can conclude that for the inequality $e\leq3v-6$ to hold, the graph must be connected. If it's not, then the above formula holds.
Community
  • 1
frabala
  • 3,732