# Prove that a graph is a maximal planar graph if and only if $e = 3v − 6$

Definition: A planar graph with no multi-edges $G$ is called a maximal planar graph if the graph formed by addition of any edge (not already in the $G$) is not planar or the graph is $K_3$ or $K_4$ (in these cases we can't add any more edges!)

I am asked to prove that a graph is maximally planar if and only if $e = 3v - 6$.

To prove the first direction (If the graph is maximal then $e = 3v-6$)

$\longrightarrow$

I use the fact that every face in a maximal planar graph is a triangle and that every edge is incident to exactly two faces, and so we have $$3f = 2e \to f = \frac{2e}{3}$$

Now I substitue this value of $f$ Euler's formula $$v + f = e + 2$$ to get $$v + \frac{2e}{3} = e + 2$$ and so we have $$e - \frac{2e}{3} + 2 = v$$ and so we have $$\frac{e}{3} = v - 2$$ and so we finally get $$e = 3v - 6$$

$\longleftarrow$

Now I have some troubles in proving that other direction, that is if $e = 3v-6$ then the graph if maximal planar. I was thinking by mathematical induction on the number of vertices. But I am lost on how to even begin, what will be the least pair of $(e,v)$ for this to work, I assume $v=1,2$ both doesn't make any sense and so $v=3$ will be the least value, and if we have $v = 3$ then we would have $e= 3 \times 3 - 6 = 3$ so we would have three edges for $3$ vertices which is basically $k_3$ and so it works as a base case.

• What's your definition of maximal planar graph? Once you know that $e\leq 3v-6$ for any planar graph with $v\geq 3$, isn't it trivial that a graph with equality there must be maximal planar? – Casteels Nov 1 '15 at 22:15
• @Casteels A planar graph with no multi-edges $G$ is called a maximal planar graph if the graph formed by addition of any edge (not already in the $G$) is not planar or the graph is $K_3$ or $K_4$ (in these cases we can't add any more edges!). – alkabary Nov 1 '15 at 22:41
• from where did you get that we knows that $e \leq 3v - 6$ for any planar graph with $v \geq 3$ ? @Casteels – alkabary Nov 1 '15 at 22:44

Assume $v\geq 3$ and fix an embedding of a planar graph and let $f_i$ be the number of faces with $i$ edges along its boundary. Since every edge is on the boundary of two (not necessarily distinct) faces we have \begin{align*} 2e&=3f_3+4f_4+5f_5+\cdots \\ &\geq 3(f_3+f_4+\dots)\\ &=3f.\end{align*}
Now apply Euler's formula to this inequality to get $e\leq 3v-6$. Your desired result follows immediately.