Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
If $G$ is not connected, the only inequalities that guarantee planarity are $e\le8$ and $v\le4$. Either one will do. –  Gerry Myerson Oct 13 '12 at 12:12
add comment

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
add comment

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

http://maths-on-line.blogspot.in/

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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