Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Upper Bound Theorem

  1. May 16, 2006 #1
    The converse of the Upper Bound Theorem would state that a graph which satisfies the inequality

    [tex]e \leq { \frac{n (v-2)}{n-2} [/tex] is planar.

    This converse is not true as seen in picture.

    Verify that the inequality [tex]e \leq { \frac{n (v-2)}{n-2} [/tex] is true for this graph.

    Using the inside-outside algorithm to show that the graph is actually non-planar.

    Attached Files:

    Last edited: May 16, 2006
  2. jcsd
  3. May 17, 2006 #2
    Does anyone know what the n stands for?
    Last edited: May 17, 2006
  4. May 17, 2006 #3
    e = edges
    v = vertices

    but what is n?
  5. May 17, 2006 #4


    User Avatar
    Science Advisor

    There is more than one "upper bound theorem" and more than one "inside-out algorithm." Why don't you start by stating them here? This will help you as well as me. Your book should tell you what n is in the theorem statement.
  6. May 17, 2006 #5
    Even using google doesn't help me to understand what n is?
  7. May 17, 2006 #6


    User Avatar
    Science Advisor

    Yes, so look in your book.
  8. May 17, 2006 #7
    Not in my book
  9. May 17, 2006 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    It will be explained wherever you got the question from.
  10. May 17, 2006 #9


    User Avatar
    Science Advisor
    Homework Helper

    I'll take a guess- perhaps n is the smallest cycle. This would correspond to the face with the smallest number of edges in a planar graph*, so you would have n<=2e/f. Apply Euler's to get rid of f (this is assuming planar) and fiddle around and you can get the inequality you've posted.

    But yea, this should be in your book, notes, or wherever this problem is from, so find it in your materials as my guess may not be what they are after (though it does look like it).

    *edit- this isn't quite right, but the minimal cycle length is <= the smallest number of edges on a face and the rest is the same.
    Last edited: May 18, 2006
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook