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!
Best Answer
Assume a plane graph with
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.