Let $e$ be the number of edges and $v \geq 3$ the number of vertices in a graph $G$. We know that if $G$ is planar, then $e \leq 3v-6$. My question is the opposite. Is there some sort of inequality that guarantees planarity?

For example, I know all trees are planar $e = v-1$. So, we could say: If $G$ is a connected graph with $e \leq v-1$, then $G$ is planar.

But, are there better known bounds that guarantee planarity? Also, I'm curious about the same question for outerplanar graphs. Again, in that case, we have an inequality that can determine when a graph is not outerplanar, but I wonder if there is one that could guarantee that a graph is outerplanar.

Assume connectedness if necessary.

  • $\begingroup$ If $G$ is not connected, the only inequalities that guarantee planarity are $e\le8$ and $v\le4$. Either one will do. $\endgroup$ Oct 13, 2012 at 12:12

2 Answers 2


By Kuratowsky's Theorem a graph is planar if it does not contain a subdivision of the $K_5$ and $K_{3,3}$ as subgraph.

You require that your graph $G$ is connected, this already needs $v-1$ edges for the spanning tree of $G$. You need at least four edges to make a $K_{3,3}$ out of a spanning tree, so you are safe if you only add 3 more edges. (The $K_5$ is worse in this sense.)

Thus your connected graph is planar, if it has $v+2$ edges. Otherwise, the $K_{3,3}$ has $v=6$ vertices, and $v+3=9$ edges and is not planar.

from a spanning tree to K_3,3 and K_5


If it is connected, $e <= v + 2$ will do. More than that, can't say. Also, make sure of the special cases mentioned above do not get in the way of the above equation.




You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .