Maximum number of edges in a planar graph 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?
 A: Proposition: If $\Gamma(E,V)$, is a planar graph (no multigraph) then
$|E| \le 3 |V| - 6$. 
Proof:
  Let us note that this does not work for a multigraph where more than one
    edge could be attached to the same two vertices. Imagine a figure (below)
of two vertices and 5 segments attached to the two vertices with no intersections
other that the ends of the segments. This figure 
    has $|E|=5$ and $|V|=2$, while the inequality $5 \le 0$ is false.

Of course $K_n$ is not a multigraph but it is good to be aware of counter-examples.
We first assume that the faces are all triangles and show the inequality 
    \begin{equation}
  2|E| \ge 3|F|   \quad \quad  (1)
\end{equation}
    For example for one face $|E|=3$ and
    $F=2$ so the equality $6=6$ is achieved. However for two faces
    (for example a rectangle with a diagonal) we have  $|E|=5$ and
    $|F|=3$, here the inequality $10 > 9$ is strict.
    We do this by induction over $|F|$ . Let us introduce a new face $|F|$ by
adding one more vertex and two more edges on the boundary of the graph (note that since all faces are triangular we can not add faces inside the graph). We need to show
    that $2| |E| +2| \ge 3| |F|+1|$. 
    \begin{equation}
  2 | |E| + 2| = 2 | E| + 4 \ge 3|F|  + 4 \ge 3|F| + 3 \ge 3| |F|+1|.
\end{equation}
Now we use Eulers equation $|V|-|E|+|F|=2$, from which $|F|=2+|E|-|V|$ and
    replacing $|F|$ in equation (1)
    \begin{equation}
  2|E| \ge 3 (2 + |E| - |V|)    
\end{equation}
    then
    \begin{equation}
  |E| \le 3|V| - 6.
\end{equation} 
Now what happens if a face is not a triangle. We need to add edges until
    making it a triangle, use equation $|E'| \le 3|V'| -6$ which is valid
    for triangles then remove the edges and find that for the new graph
    $|E| \le 3|V| - 6$ is a valid inequality. After adding edges to make all faces 
    triangles we have $|E'| \le 3|V'| -6$ where $|E'|$ and $|V'|$ are the number of edges and
    vertices of the new triangulated graph. When we remove one edge 
    which is common to two triangular faces, we end up with a quadrilateral.
    The graph has one less edge without removing any vertex. In general,
    we remove edges but no vertices to go from the triangulated to the original
  graph, so $|E| < |E'|$ and $|V|= |V'|$. That is,
  \begin{equation}
  |E| < |E'| \le 3 | V'| - 6 = 3 |V| - 6,
  \end{equation}
  from which the proposition is shown.
Now, a $K_n$ graph has $n$ vertices so, $|E| \le 3n - 6$.
However the number of edges of $K_n$ can be exactly counted. Put the vertices
in a unit circle equally spaced. That is, on the $n$ complex roots of the
equation $z^n -1 = 0$. Each vertex can visit exactly $n-1$ other vertices, 
for a total of $n(n-1)$. But each edge was counted twice (from $v_i$ to $v_j$ and
from $v_j$ to $v_i$) so the exact maximum is $n(n-1)/2$.
It is interesting that this serves to show the inequality $3n-6 \le n(n-1)/2$. . Use gnuplot or any graph tool to illustrate this. Of course the only solution is for $n=3$, where we have a single triangle. After that the inequality is strict. 
A: 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.
