Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie
Hi there,
There is an issue with role permissions that is being worked on at the moment.
If you are having trouble with access or permissions on regional forums please post here to get access: https://www.boards.ie/discussion/2058365403/you-do-not-have-permission-for-that#latest

graph theory Q

  • 11-05-2012 11:42am
    #1
    joey12345
    Registered Users, Registered Users 2 Posts: 49 ✭


    does anyone know much about this question?

    can the following degree sequence 3,4,4,5,5,5 be planar?

    i dont want the answer just looking through my notes here and i cant find anything thats of help.

    is it something to do with the 3 vertex of degree 5?

    part (a) of the question is in relation to eulers formula v-e+r=2

    so im guessing its to do with some variation of this any help is greatly appreciated.
    Tagged:


Comments

  • #2
    CJC86
    Registered Users, Registered Users 2 Posts: 360 ✭✭CJC86


    As you said, it has something to do with Euler's formula. For planar graphs, v-e+r=2 where v is the the total number of vertices, e is the total number of edges and r is the number of regions (when drawn as a planar graph), including the infinite external region.

    You have the degree sequence, so you can count how many vertices you have, this is the v in Euler's formula.

    How do you get the total number of edges, e, from the degree sequence? Hint: each edge must go out of one vertex and in to another vertex.

    Now the r is trickier, but you should have some inequality to tell you the limit on r, given that you know e.


  • #3
    joey12345
    Registered Users, Registered Users 2 Posts: 49 ✭joey12345


    CJC86 wrote: »
    As you said, it has something to do with Euler's formula. For planar graphs, v-e+r=2 where v is the the total number of vertices, e is the total number of edges and r is the number of regions (when drawn as a planar graph), including the infinite external region.

    You have the degree sequence, so you can count how many vertices you have, this is the v in Euler's formula.

    How do you get the total number of edges, e, from the degree sequence? Hint: each edge must go out of one vertex and in to another vertex.

    Now the r is trickier, but you should have some inequality to tell you the limit on r, given that you know e.

    Thanks for the reply. I knew it was something easy but it's one of them things that was really annoying me. I just drew it up and seen it was homeomorphic to k3,3 and I think it's called kuratowskis theorem, Anyway thanks again for the reply


Advertisement