# Suppose G is an unconnected planar graph, with v nodes, e edges, and f faces, where v ≥ 3.

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

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

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