Maximum number of edges in a planar graph

Question

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?

Answer 1

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.

Answer 2

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.