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?

  • $\begingroup$ Please see this tutorial on how to typeset mathematics on this site. A minor computational mistake: $30 \cdot 3 - 6 = 8\color{red}{4}$. $\endgroup$ – N. F. Taussig Jun 20 '15 at 19:47
  • 1
    $\begingroup$ 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? $\endgroup$ – hmakholm left over Monica Jun 20 '15 at 19:49
  • $\begingroup$ @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? $\endgroup$ – 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.

planar triangular with 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.