May14-10, 12:01 AM
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)
(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!
|Register to reply|
|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|