Can a Simple Graph with No K5-Minor Have More Than Five Vertices?

[ploppers]

Homework Statement

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.

Homework 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

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!

 

[mighty2000]

Thank you for your post. I understand that you are struggling with proving the statement that if G is a simple graph with no K5-minor and |V(G)| does not equal 0, then G has a vertex at most 5. Let me try to guide you through the proof.

First, let's recall the statement that you have proved earlier in the problem set: |E(G)| <= 3|V(G)| - 6 for |V(G)| >= 3. This means that for any simple graph with at least 3 vertices, the number of edges is at most 3 times the number of vertices minus 6. This is a very useful fact that we will use in our proof.

Next, let's consider the case where |V(G)| = 1 or 2. In this case, it is clear that G has a vertex at most 5, since there are only 1 or 2 vertices in the graph. So, we can assume that |V(G)| >= 3.

Now, let's suppose for contradiction that G has more than 5 vertices. This means that |V(G)| > 5. Using the fact that |E(G)| <= 3|V(G)| - 6, we can write:

|E(G)| <= 3|V(G)| - 6 < 3|V(G)| - 3

Since |V(G)| > 5, we can replace it with 6 and write:

|E(G)| < 3(6) - 3 = 15

This means that G has less than 15 edges. But we know that G has no K5-minor, which means that G cannot have a complete graph with 5 vertices as a minor. The complete graph with 5 vertices has 10 edges, which is more than 15. This contradicts our previous statement that G has less than 15 edges. Therefore, our assumption that G has more than 5 vertices must be false.

Hence, we can conclude that if G is a simple graph with no K5-minor and |V(G)| does not equal 0, then G has a vertex at most 5.

I hope this helps. Keep up the good work on your problem set!