By adding edges we can assume that $G$ is a triangulation (note that if we add edges the minimum degree only increases and if we find an edge $\{x, y\}$ such that $\deg(x) + \deg(y) \le 11$ in the new graph, this edge will also be present in the original graph, since otherwise one of its endpoints would have degree smaller than $5$ in the original graph).

Let $V$ be the set of vertices, $E$ the set of edges, and $F$ the set of faces of our triangulation. Let $d(v)$ be the degree of $v \in V$ and let $d(f)$ be the number of edges on the boundary of $f$. Here, if $e \in E$ is on the boundary of only one face, then we count it two times. Hence,
$$\sum_{f} d(f) = 2|E| = \sum_{v \in V} d(v)$$
Thus, by Euler's formula, we have
$$\sum_{v \in V} (6 - d(v)) = \sum_{f} (6 - 2d(f)) + \sum_{v \in V} (6 - d(v)) = 6|F| - 4|E| + 6|V| - 2|E| = 12$$
since for every face $d(f) = 3$. Let us give a charge $6 - d(v)$ to every vertex $v \in V$. The total charge is $12$. The only vertices with positive initial charge are vertices satisfying $d(v) = 5$. Now we discharge the system using a single rule: every vertex of degree $5$ gives charge $\frac{1}{5}$ to each of its neighbors. Clearly the total final charge is still $12$. Thus there are vertices with positive final charge. Suppose $v$ is such a vertex. Then its final charge $c(v)$ satisfies
$$0 < c(v) \le 6 - d(v) + \frac{1}{5}d(v) = 6 - \frac{4}{5}d(v).$$
Thus $d(v) \le 7$. Now we consider three cases.

i. Suppose $v$ with positive final charge satisfies $d(v) = 6$. Then its initial charge was $0$ and thus this vertex must have gained some charge. So, one of its neighbors $u$ has degree $5$ and $\{u, v\}$ is the desired edge.

ii. Suppose $v$ with positive final charge satisfies $d(v) = 5$. Then in the discharging process this vertex gave all its charge to its five neighbors. But since the final charge is positive, it must have gained some charge from a vertex of degree $5$. Thus, one of its neighbors $u$ has degree $5$ and so $\{v, u\}$ is the desired edge.

iii. Suppose $v$ with positive final charge satisfies $d(v) = 7$. Since the initial charge of $v$ was $-1$, $v$ gained charge from at least $6$ of its neighbors, so it has at least $6$ neighbors with degree $5$. There is one more neighbor of $v$ whose degree we do not control. Since $G$ is a triangulation, the neighbors of $v$ form a cycle and clearly on this cycle there are two adjacent vertices $u_1$ and $u_2$ of degree $5$. Thus $\{u_1, u_2\}$ is the desired edge.

$\boxed{}$