What is the maximum number of edges a planar subgraph of $K\_n$ can have? Is there a simple way to calculate this if not, are there some values of n for which this is easier to find out?



Maximum number of edges in a planar graph
Suppose the graph has $n$ vertices, $m$ edges, and $f$ faces. By Euler's formula we know that
$$n - m + f = 2$$
Now presume there are at least three vertices. Every face must be a triangle, otherwise you can increase the number of edges by dividing a face with an edge. Since every edge borders two faces, $2m=3f$. Therefore
$$n - m + \frac{2}{3}m = n - \frac{1}{3}m=2$$
or
$$m = 3n-6$$


This can be achieved by triangulating the inside and outside of an $n$-gon. There are $n$ edges that make the $n$-gon, $n-3$ that triangulate the inside, and $n-3$ that triangulate the outside.


Please delete. I didn't see Professor Elkies comment.


