In the simple planar graph G the degree of each vertex is at least 5. Show that in this case G contains at least 12 vertices of degree 5.

Question

In the simple planar graph G the degree of each vertex is at least 5. Show that in this case G contains at least 12 vertices of degree 5.

I tried to solve it in this way:

we know that for simple planar graph to exist this statement ($ e <= 3n - 6 $ ) must hold. n - number of vertices. I found that $ 5n = 2e $ from handshake theorem and then i found that $ e=5n/2 $ . Now I have no idea what to do next. My guess is somehow prove it with help of number of edeges...

Thanks for help!

Answer 1

We're trying to count how many vertices there are of a particular degree - so how about naming the numbers of vertices of each degree. Let $n_5$ be the number of vertices of degree $5$, $n_6$ be the number of vertices of degree $6$, and so on. What do the vertex and edge counts look like in terms of these?

Answer 2

Since the minimum degree is at least 5, n=6 , and we know that for a simple planar graph with$n \geq 3$, $m \leq 3n-6$. Since minimum degree is 5. $m \geq \frac{5n}{2}$. So , $ 5n/2\leq 3n-6$
$ \Rightarrow5n \leq 6n-12 $ which gives $ n \geq 12$