# 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.

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.

• Sorry, I modified it now. Commented May 23, 2022 at 8:12
• licheng's comment above refers to when I said the link didn't work. Now it does work. just adding this since I realized that without it the comment of licheng has no meaning. Commented May 23, 2022 at 8:16
• So I haven't worked out all of the details, but I would start as follows. First, note that it suffices to consider the case of 13 vertices and 33 edges. Otherwise, by Euler's formula, the graph is not planar. Now in the case of 33 edges, we have 12 vertices of degree 5 and a single vertex $v$ of degree $6$. Start with $v$ and its neighbors. So we have a $K_{1,5}$ and need to add additional edges. There are also $6$ vertices left over. By Euler's formula, there can be at most 12 edges between these 6 remaining vertices. So at least 3 edges have to be between the $K_{1,5}$ and other 6 vertices. Commented May 24, 2022 at 6:34
• With some case analysis, it seems plausible to force either a $K_{3,3}$ or $K_{5}$. Commented May 24, 2022 at 6:35

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

1. all $$v_i$$ are pairwise different,

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

3. 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).

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

2. 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).

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.