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

planar-graphs

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

Best Answer

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.