Number of vertices in a planar graph

Question

For which values of $k$ can you prove the following statement? There exists an $n$ such that any planar graph on at least n vertices contains at least $k$ vertices of degree at most $5$. Could it hold for every $k$?

Answer 1

Summary: $k=4$ is the largest $k$. We can eliminate $k \leq 2$ using Euler's Formula and the Handshaking Lemma. We can eliminate $k=3$ with some case analysis. And when $k=4$, there's a construction of a family of planar graphs with $n-4$ degree-$6$ vertices and $4$ degree-$3$ vertices.

---

A graph with $q:=n-k$ vertices of degree $\geq 6$ has at least $\tfrac{1}{2} 6q=3q$ edges, by the Handshaking Lemma. Euler's Formula thus implies that a $n$-vertex planar graph has $3q \leq 3n-6$, or equivalently $q \leq n-2$. This proves $k \geq 2$.

If $k=2$ and the small degrees are $d_1$ and $d_2$, then by bounding the sum of the degrees, we get $$ 6(n-2)+d_1+d_2 \leq 2e \leq 6n-12 $$ which implies $d_1$ and $d_2$ are both $0$. We can delete these two isolated vertices to contradict Euler's Formula. So $k \geq 3$.

If $k=3$ and the small degrees are $d_1$, $d_2$, and $d_3$, then $$6(n-3)+d_1+d_2+d_3 \leq 2e \leq 6n-12.$$ That is, $d_1+d_2+d_3 \leq 6$.

If we have an isolated vertex, we delete it and end up back in the $k=2$ case. If we have a vertex of degree $2$, we can contract it with one of its neighbors, and end up back in the $k=2$ case. Either way, we reach a contradiction.

If we have a vertex of degree $1$ then... If its neighbor has degree other than $6$, than we can delete the degree-$1$ vertex and end up in the $k=2$ or $k=1$ case, reaching a contradiction. Otherwise, we still delete it, but we remain in the $k=3$ case, but with a degree-$5$ vertex, but then we contradict $d_1+d_2+d_3 \leq 6$.

Thus $d_1$, $d_2$, and $d_3$ are all at least $3$, contradicting $d_1+d_2+d_3 \leq 6$.

Hence $k \geq 4$.

Finally, I think the construction Henning Makholm and Jack D'Aurizio seem to be talking about in the comments is:

1. Take a tetrahedron,
2. subdivide each edge once, and
3. connect newly created vertices that share a face that was on the original tetrahedron.

Then repeat steps 2 and 3. (Projecting onto a sphere or plane as desired.) Here's an attempt at a drawing:

We always create vertices of degree $6$, and we have exactly $4$ vertices of degree $3$. Thus construction implies $k \leq 4$.