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 minors question!

  1. May 13, 2010 #1
    1. The problem statement, all variables and given/known data

    Prove that, if G is a simple graph with no K5-minor and |V(G)| Does not = 0, then G has a vertex at most 5.

    2. Relevant equations
    |E(G)| <= 3|V(G)| - 6 for |V(G)| >= 3 (Proved by earlier part of problem set)

    Handshake theorem
    (I don't believe we are allowed to use hadwiger's conjecture

    3. The attempt at a solution

    Well I first used the handshake theorem to show that the sum of the degrees in G are equal to 2 times the edges in G.
    Sum(Deg (v)) for all v in G = 2 |E(G)|

    use V average and replace |E(G)| with 3|V(G)| - 6 so:

    Vaverage |V(G)| <= 2(3|V(G)| - 6) = 6|V(G)| - 12

    divide by |V(G)|

    = 6 - 12/|V(G)|

    now for any V(G) less than 3, we can see it intuitively. However...I can't have |V(G)| > 12.....Help please! I've been a little frustrated.

    Thanks for your time!
  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