How to prove that there is no planar graph on $13$-vertices with minimum degree $5$? We know that Euler's formula produces the following result.
If $G$ is a planar graph with minimum degree  $5$, then it has at least $12$ vertices.
I  find that the planar graph $H$ on  $13$ vertices with minimum degree $5$ does not exist by using plantri program.
The web version of plantri is as follows.

*

*http://combos.org/plantri
But I'm not sure how to provide evidence for it.

I can only prove that there must be $12$ vertices of degree $5$ and one vertex of degree $6$ in such graphs.
Given a planar graph $G$ of order $n$ and size $m$, $n$ and $m$ must satisfy:
$$
m\le 3n-6.
$$
Let $n_5$ be the number of vertices that have degree exactly $5$.
If $\delta(G)=5$,  then we have
$$
2(3n-6)\ge n_5\times 5+ 6(n-n_5).
$$
This immediately implies $n_5 \ge 12$.
Recall that graph $H$ is a planar graph on 13 vertices with minimum degree $5$. Combing with the fact that the number of vertices of odd degree is even (by the handshake lemma), we get that $H$ contains $12$ vertices with  degree $5$ and one vertex with  degree $6$. But then I couldn't do anything else.
 A: My reasoning is a bit long. In spite of this I had to omit some details.
Let $G$ be a planar graph with $13$ vertices and the degree of each vertex of $G$ be at least $5$.
We can assume that each face of $G$ is a triangle and then each edge of $G$ lies exactly in two faces.
We will prove that the existence of such a graph leads to a contradiction.

Lemma 1. The graph $G$ has exactly one vertex of degree $6$ and $12$ vertices of degree $5$.

We assume that the vertices of $V(G)$ lie on some plane, and the edges of $G$ are some curves connecting the vertices, and any two edges have no common points in the plane except vertices.

Lemma 2. If $T=x_1x_2x_3$ is a triangle in $G$ (that is, $x_1,x_2,x_3\in V(G)$ and $x_1x_2,x_2x_3,x_3x_1\in E(G)$), then either
no vertices of $G$ lie inside $T$, or all vertices of $G$ lie inside $T$ (except
vertices $x_i$ of course).
In other words, each triangle of graph $G$ is an face.

Proof.
Let $k$ vertices of graph $G$ lie inside $T$ and $k>0$.
Obviously, $k\geq3$.
We consider only the case when $k=5$. Leave the cases $k=3,4$ as an easy exercise.
If $k>5$, then $l=10-k\leq4$ and there are exactly $l\leq4$ vertices outside $T$.
Hence the same arguments show that it should be $l=0$ or $k=10$.
So let $k=5$.
Let $v_1,v_2,v_3\in V(G)$ and the faces $x_1x_2v_3$, $x_2x_3v_1$,
and $x_1x_3v_2$ lie inside triangle $T$.
It is easy to see that $v_1,v_2,v_3$ are pairwise different
(if for example $v_1=v_2$, then $T$ splits into three triangles
and no more than $4$ vertices lie inside one of them).
It follows that in the induced graph $H$ with set of vertices
$\{x_1,x_2,x_3,v_1,v_2,v_3,v_4,v_5\}$,
where $v_3,v_4$ lie inside $T$, we have $\deg_H(x_i\geq4)$, $i=1,2,3$.
Then by the handshake lemma the following holds
$$
2|E(H)|\geq3\cdot4+5\cdot5=37\ \Rightarrow\ E(H)\geq19.
$$
On the other hand
$$
|E(H)|\leq3\cdot8-6=18.
$$
We get a contradiction.

Lemma 3. If $Q=x_1x_2x_3x_4$ is a quadrilateral in $G$ ( i.e., $Q$ is a cycle in $G$ of length $4$ and $x_1x_2,x_2x_3,x_3x_4,x_4x_1\in E(G)$),
then either no vertices lie inside $Q$, or all vertices lie
inside $Q$ (except vertices $x_i$).

Proof.
Let $k$ vertices of graph $G$ lie inside $Q$ and $k>0$.
It is sufficient to consider the cases $k=1,2,3,4$.
For $k>4$ we have $l=9-k\leq4$ and we can go to the outer points of $Q$.
Then it is easy to see that $k\geq3$.
Of the two remaining cases we will consider only the case $k=4$.
As in the previous lemma, let $x_1x_2v_1$, $x_2x_3v_2$, $x_3x_4v_3$, $x_4x_1v_4$ be faces lying inside $Q$.
It is easy to see that

*

*all $v_i$ are pairwise different,


*each $v_i$ is adjacent only to two vertices of $Q$,


*the induced graph $F$ with set of vertices $v_i$ is a cycle.
It follows that $\deg(v_i)<5$. Contradiction.

Lemma 4. Let $v\in V(G)$, $\deg(v)=6$ and $u_i$ ($1\leq i\leq 6$) be all neighbors of the vertex $v$. Then the induced graph $H$ with
set of vertices $u_i$ is a cycle.

Proof.
This follows from Lemmas 2 and 3.
Then we reason like this. Let $v\in V(G)$, $\deg(v)=6$.
Let $u_i$ ($1\leq i\leq 6$) be all neighbors of the vertex $v$.
Let $u_iu_{i+1}w_i$ ($i=1,\ldots,6$, $u_7=u_1$) be faces lying inside $H$ (see figure).


*

*The vertices $w_i$ are pairwise different and distinct from vertices $u_i$, $v$.


*If vertex $w_1$ is adjacent to vertex $w_3$, then there are vertices inside and outside the quadrilateral
$w_1w_3u_3u_2$ (contrary to Lemma 3).


*If vertex $w_1$ is adjacent to vertex $w_4$, then vertex $w_2$ is adjacent to vertex $w_4$
(otherwise $\deg(w_2)<5$). We come to the case discussed in 2).
This concludes our proof.
