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
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100

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