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
Final pieces to the circadian clock puzzle found
A spray-on light show on four wheels: Darkside Scientific
How an ancient vertebrate uses familiar tools to build a strange-looking head

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