Prove Graph Theory: All Vertices > 4, At Least 12 Degree 5

[DianaSagita]

Homework Statement

If all vertices of planar graph have degrees greater than 4, prove if
that graph has at least 12 vertices with degree of 5.

Homework Equations

d1+d2+...+dn= 2*m (m - number of edges, di-degree of i-vertex)
f=2-n+m, f - number of faces, n-number of vertices

The Attempt at a Solution

I did this...
2*m>= 12*5+(n-12)*6
2*m>=3*f (every face defined with at least 3 edges, and every edge goes between 2 faces...)
I'm not sure what to do next... :(

 

[mighty2000]

Dear student,

Thank you for your post. Your approach is on the right track, but there are a few more steps that need to be taken to prove that a planar graph with all vertices having degree greater than 4 must have at least 12 vertices with degree 5. Here is a possible solution:

First, let us assume that the graph has n vertices and m edges. Since all vertices have degree greater than 4, we can write the following inequality:

d1 + d2 + ... + dn ≥ 5n

where di represents the degree of the ith vertex. Rearranging, we get:

2m = d1 + d2 + ... + dn ≥ 5n

Next, using the fact that every face is defined by at least 3 edges and every edge is shared by 2 faces, we can write the following inequality:

2m ≥ 3f

where f represents the number of faces in the graph.

Now, using the Euler's formula for planar graphs, we have:

f = 2 - n + m

Substituting this into the previous inequality, we get:

2m ≥ 3(2 - n + m)

Simplifying, we get:

2m ≥ 6 - 3n + 3m

Rearranging, we get:

3m - 2m ≥ 6 - 3n

m ≥ 6 - 3n

Since m represents the number of edges and each edge is shared by 2 vertices, we can write:

2m = d1 + d2 + ... + dn

Substituting this into the previous inequality, we get:

d1 + d2 + ... + dn ≥ 6 - 3n

Since we already know that d1 + d2 + ... + dn ≥ 5n, we can combine these two inequalities to get:

5n ≥ 6 - 3n

8n ≥ 6

n ≥ 6/8

n ≥ 3/4

Since n is an integer, we can conclude that n ≥ 1. Therefore, the graph must have at least 1 vertex. But since we have already established that all vertices have degree greater than 4, the graph must have at least 5 edges (since each vertex has at least 5 edges connected to it). This means that the graph must have at least 6 vertices (since each edge connects