(adsbygoogle = window.adsbygoogle || []).push({}); 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!

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Graph theory minors question!

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**