0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What have you tried so far? Are you aware of any property of planar graphs, that would help you? $\endgroup$ – frabala Mar 25 '14 at 0:57
  • $\begingroup$ Hint: Apply the formula $e\leq 3v-6$ to each connected components of $G$. $\endgroup$ – Paul Mar 25 '14 at 1:29
  • $\begingroup$ @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. $\endgroup$ – Giorgia Mar 25 '14 at 1:55
0
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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