Prove an upper bound on the maximal number of edges of a planar graph.

Question

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!

Answer 1

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.

Answer 2

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