1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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

Can you help with the solution or looking for help too?

Similar Discussions: Graph theory minors question!
  1. Graph Theory (Replies: 0)

  2. Graph theory (Replies: 0)

  3. Graph theory question (Replies: 0)

  4. Graph Theory (Replies: 0)