Prove an upper bound on the maximal number of edges of a planar graph. I'm trying to prove the following:
If G is a planar graph then the number of edges can't be e>3v-6.
I want to assume that the graph is planar and its number of edges is e>3v-6. and reach a contradiction.
My attempt:
If G is planar then it satisfies the euler theorem, meaning it satisfies:
v-e+f=k+1.
v is the number of vertices.
e is the number of edges.
f is the number of faces.
k is the number of connected components.
Now, every face is a triangle, because otherwise we could add a new edge in such a way that the graph would remain planar, so 3f=2v.
So we get:
(5/3)v-e=k+1
But here I lost my way, I tried going in different directions to try and "break" the euler formula but didn't succeed.
Thanks!
 A: Assume a plane graph with


*

*$v$ vertices.$\\[4pt]$

*$e$ edges.$\\[4pt]$

*$f$ bounded faces.


Our goal is to show $e\le 3v-6$.

If $e\le 1$, the inequality can fail. For example, consider a path of length $1$.

If $e=2$, then $v\ge 3$, hence $e=2 < 3=3(3)-6\le 3v-6$.

Finally suppose $e\ge 3$. 

Let $k$ be the number of components.

For $1\le i\le k$, let $v_i,e_i,f_i$ be the respective number of vertices, edges, and bounded faces for the $i$-th component.

Then by Euler's formula we have $v_i-e_i+f_i=1$ for all $i$, hence $v-e+f=k$.

If we include the unbounded face, each face has at least $3$ edges, and each edge belongs to at most two faces, hence $3(f+1)\le 2e$.

Then $3f\le 2e-3$,$\;$hence
\begin{align*}
&v-e+f=k\\[4pt]
\implies\;&v-e+f\ge 1\\[4pt]
\implies\;&3v-3\ge 3e-3f\\[4pt]
\implies\;&3v-3\ge 3e-(2e-3)\\[4pt]
\implies\;&e\le 3v-6\\[4pt]
\end{align*}
as was to be shown.
A: Add edges as long as it is possible.
Then $k=1$ as otherwise you can add an edge between components, so
$$v+f=e+2 $$
or
$$ 3v-6=3e-3f$$
and with $3f=2e$
$$ 3v-6=3e-2e=e$$
