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: Graph theory, prove

  1. Jan 31, 2010 #1
    1. The problem statement, all variables and given/known data

    If all vertices of planar graph have degrees greater than 4, prove if
    that graph has at least 12 vertices with degree of 5.


    2. Relevant equations

    d1+d2+...+dn= 2*m (m - number of edges, di-degree of i-vertex)
    f=2-n+m, f - number of faces, n-number of vertices

    3. The attempt at a solution

    I did this...
    2*m>= 12*5+(n-12)*6
    2*m>=3*f (every face defined with at least 3 edges, and every edge goes between 2 faces...)
    I'm not sure what to do next... :(
     
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted