Number of vertices in a planar graph 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$?
 A: 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:


*

*Take a tetrahedron,

*subdivide each edge once, and

*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$.
