Register to reply 
Graph theory minors question! 
Share this thread: 
#1
May1310, 11:01 PM

P: 15

1. The problem statement, all variables and given/known data
Prove that, if G is a simple graph with no K5minor and V(G) Does not = 0, then G has a vertex at most 5. 2. Relevant equations E(G) <= 3V(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 3V(G)  6 so: Vaverage V(G) <= 2(3V(G)  6) = 6V(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! 


Register to reply 
Related Discussions  
Question about Minors in engineering  Academic Guidance  0  
Graph theory question  Calculus & Beyond Homework  0  
Basic Graph Theory Question  General Math  6  
Graph theory: quick question(s)  General Math  5  
Question on Graph theory  Linear & Abstract Algebra  26 