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.
$\endgroup$ 12 Answers
$\begingroup$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.
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.
Salahuddin
$\endgroup$
