# In a complete graph of 30 nodes, what is the smallest number of edges that must be removed to be a planar graph?

I know that a planar graph can not shrink in a $K_{3,3}$ (bipartite graph with $6$ vertices) or a graph $K_5$, and also can not contain cycles of length $3$.

There is a theorem that in a graph is flat:

edges $\leq 3 \cdot$ vertices $- 6$

If this is true, it is easy to calculate the minimum number of edges that must be removed to be a planar graph:

$30 \cdot 3 - 6 = 86$

In a graph $K_{30}$ we have a total of $\frac{30 \cdot 29}{2}$ edges.

The minimum number of edges that must be removed:

$$\frac{30 \cdot 29}{2} - (30 \cdot 3 - 6)$$

Is this true?

• Please see this tutorial on how to typeset mathematics on this site. A minor computational mistake: $30 \cdot 3 - 6 = 8\color{red}{4}$. – N. F. Taussig Jun 20 '15 at 19:47
• If your theorem is true then you know that a planar graph on 30 vertives cannot have more than 84 edges, but do you know that 84 edges are possible? – hmakholm left over Monica Jun 20 '15 at 19:49
• @Blunt: Why can a planar graph not contain cycles of length 3? If you draw just a triangle, is planar, isn't it? Or did I misunderstand you? – Moritz Jun 21 '15 at 7:47

So we have theoretically that $\geqslant \binom{n}{2}-(3n-6)=435-84=351$ edges must be deleted, but that doesn't mean it is sufficient: one still needs to demonstrate that some way of deleting $351$ edges gives a planar graph.
In general, the upper bound on the number of edges $3n-6$ (for $n \geq 3$) will be achieved by planar triangulations (i.e., every face is a triangle). In the following drawing, we have $28$ pink vertices and $2$ blue vertices marked with their degrees. It's a planar triangulation on $30$ vertices.
By the Handshaking Lemma, the number of edges is $$\tfrac{1}{2} (3+\overbrace{4+4+\cdots+4}^{26}+3+29+29)=84.$$ The drawing shows its planar.
Thus, if we take the complete graph, and delete from it the non-edges above, we delete $351$ edges and create a planar graph.