Does a maximal planar graph with number of vertices $\ge$ 6 always have a vertex of degree exactly 5?

245 Views Asked by At

In a proof of a theorem, my professor wrote that since $G$ is a maximal planar graph with $|V|\ge6$, so, there exists a vertex of degree 5. I know the result that every planar graph has a vertex of degree atmost 5, but I am not sure about the result used by my professor. I googled it but couldn't find any such result.
Is the result true and if it is true then how to prove it ?

2

There are 2 best solutions below

1
On BEST ANSWER

It should be incorrect. We can only say that the minimum degree is less than or equal to 5, and the maximum degree is at least 5 (using the average degree as caduk mentioned). However, we can still find counterexamples that do not contain vertices with degree 5.

enter image description here

![enter image description here

3
On

It is true that a maximum planar graph has a vertex of degree at least $5$ if $v = |V| > 6$.

We know that a maximal planar graph has $e = 3v-6$ edges. The average degree of a maximal planar graph is thus $\frac{2e}{v} = 6 - \frac{12}{v}$ (the sum of degrees of a graph is $2e$). If $v > 6$, then the average degree is strictly above $4$, so there is at least one vertex of degree at least $5$.

If $v = 6$, the average degree is exactly $4$, so we need a $4$ regular graph to have a counter example. The only possible one is the octahedron graph.

See licheng answer for bigger graphs that have no vertices of degree $5$.