Register to reply

Graph theory minors question!

by ploppers
Tags: graph, minors, theory
Share this thread:
May13-10, 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 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!
Phys.Org News Partner Science news on
FIXD tells car drivers via smartphone what is wrong
Team pioneers strategy for creating new materials
Team defines new biodiversity metric

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