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

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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted
Similar Discussions: Graph theory minors question!
  1. Graph theory question (Replies: 0)

  2. Graph Theory (Replies: 4)

  3. Graph theory question (Replies: 1)