# Upper Bound Theorem

• May 16th 2006, 12:52 PM
Natasha1
Upper Bound Theorem
The converse of the Upper Bound Theorem would state that a graph which satisfies the inequality $e \leq { \frac{n (v-2)}{n-2}$ is planar.

This converse is not true as seen in picture.

Verify that the inequality $e \leq { \frac{n (v-2)}{n-2}$ is true for this graph. Once done, use the inside-outside algorithm to show that the graph is actually non-planar.
• May 17th 2006, 08:38 AM
Natasha1
e = edges
v = vertices

but what is n?
• May 22nd 2006, 05:39 AM
DangerMan
perhaps it stand for number of points.
• May 22nd 2006, 05:59 AM
Natasha1
could someone work out the inside outside algorithm? I'm stuck