2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Casteels Nov 1 '15 at 22:15
  • $\begingroup$ @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!). $\endgroup$ – alkabary Nov 1 '15 at 22:41
  • $\begingroup$ from where did you get that we knows that $e \leq 3v - 6$ for any planar graph with $v \geq 3$ ? @Casteels $\endgroup$ – alkabary Nov 1 '15 at 22:44
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.