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

Question

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?

Answer 1

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.