How can I prove that there is not a 5-regular planar graph with 14 vertices.

Question

I tried several approaches, but I cannot prove that such graph doesn't exists. Any hints?

The question How many nodes are there in a $5$-regular planar graph with diameter $2$? is related, but the answers presented there can't solve my problem (to the best of my knowledge).

For example, by using the handshaking theorem I get the number of edges ($m=35$), by using $m\leq3n-6$ I get that is possible $n\geq12$ and the number of faces is $23$.

I found an article Recursive generation of 5-regular graphs by M. Hasheminezhad, B. D. McKay and T. Reeves. But there is not an explanation about why a $5$-regular planar graph with $14$ doesn't exists.

Answer 1

It was proved by Owens that the only regular planar graphs of order $n$ and degree $d$ are the ones satisfying the Euler property: $m\leq 3n-6$, so in this case, $nd \leq 6n - 12$, at the exception at $d=4$ and $n=7$, and $d=5$ and $n=14$.

Owens, A. B., On the planarity of regular incidence sequences, J. Comb. Theory, Ser. B 11, 201-212 (1971). ZBL0237.05102.

To prove that $d=5$ and $n=14$ is not planar realizable, suppose there exist a realization. You can find the number of edges $m=5\times4/2 = 35$ and with Euler formula the number of faces $f=m-n+2 = 35-14+2=23$. A maximal planar graph has $3n-6 = 36$ edges so there is only one edge missing to be a triangulated graph. We conclude that the graph should have $22$ triangle faces and one $4$ sided face. Let's try to build it:

The construction of a triangulation with prescribed degrees is forced. Fix a face, then for each edge of the current face, if the adjacent vertices both lack some edges to get the required degree, add an edge on each vertex to form a triangle. The face ends up with one more edge. If only one the adjacents vertices lacks an edge to get the required degree, add an edge on it, and link it to the second vertex on the other side to form a triangle. The inner face ends up with one less edge. If both adjacents vertices already have the required degree, the current edge can't belong to a triangle, hence a contradiction.

Here, we fix the outer face to be the $4$ sided face. The inner graph is triangulated, so the construction should be unambiguous. If we follow the construction as described above, we end up with a contradiction, because we would need more than 14 vertices to complete the triangulation.

Answer 2

I propose another solution to this problem. It seems to me that it is somewhat easier than Owens' solution.

Theorem. A graph with 14 vertices each having degree 5 is non-planar.

Suppose to the contrary that there exists a planar graph $G$ with $14$ vertices and the degree of each vertex of $G$ is $5$. Hereafter, we assume that the graph $G$ is already embedded in the plane.

Lemma 1. The graph $G$ has exactly one $4$-sided face.

Let us add to $G$ another edge connecting opposite vertices of the $4$-sided edge. The new graph is planar and we denote it by the same symbol $G$. The graph $G$ has the following properties:

1. it has twelve vertices of degree $5$ and two vertices of degree $6$;

2. vertices of degree $6$ are adjacent;

3. each face of $G$ is a triangle and each edge of $G$ lies exactly in two faces.

Each simple cycle $C$ of a plane graph divides the set of its vertices into three parts: $V_{in}(C)$ vertices lying inside, $V_{out}(C)$ vertices lying outside and $V(C)$ vertices of the cycle. In our graph $G$ the principle "either all or nothing" is true for cycles of length $3$ and $4$. This is proved by Lemmas 2 and 3.

Lemma 2. Each triangle of graph $G$ is an face.

Proof. See Lemma 2 in How to prove that there is no planar graph on $13$-vertices with minimum degree $5$?

Lemma 3. If $Q$ is a simple cycle in $G$ of length $4$, then either no vertices lie inside $Q$, or all vertices lie inside $Q$ (except vertices of $Q$).

Proof. Suppose, to the contrary, that $|V_{in}(Q)|>0$ and $|V_{out}(Q)|>0$. It is clear that $|V_{in}|>1$. It suffices to consider the cases where $|V_{in}(Q)|=2,3,4,5$. The first three cases are considered in How to prove that there is no planar graph on $13$-vertices with minimum degree $5$? Let $|V_{in}(Q)|=5$. I will point out only the main points (see Fig. 1):

1. there are 4 faces with vertices $u_i$, $i=1,2,3,4$;

2. each $u_i$ is adjacent to exactly two vertices $x_i$;

3. vertex $v$ is adjacent to exactly one vertex $x_i$ (let it be $x_1$));

4. vertex $v$ is not adjacent to $u_2$ and $u_3$.

It follows that $\deg(v)<5$, which is a contradiction. (Note that to prove items 2, 3, 4 we have to use Lemma 2 and Lemma 3 for the cases when $V_{in}(Q)\leq4$.)

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

This statement was discussed in How to prove that there is no planar graph on $13$-vertices with minimum degree $5$?

We are ready to finish the proof of our claim. Let the vertex $v$ be chosen as stated in lemma 4 and additionally $\deg(u_1)=6$. Let $w_i$ be the vertices of faces bounding the edges of the cycle $u_1\ldots u_6$ (see Fig. 2). It follows from Lemmas 2 and 3 that all $w_i$, $u_i$ are pairwise distinct, and also the vertex $w$ is distinct from vertices $w_i$ and $u_i$.

It follows from Lemmas 2 and 3 that $$ ww_2,ww_5,w_1w_3,w_2w_4,w_3w_5,w_4w_6,w_5w_1,w_6w_2\notin E(G). $$ Then $w$ is adjacent to $w_1$, $w_3$, $w_4$, and $w_6$. We see that $w_2$ and $w_5$ cannot be adjacent, and then $\deg(w_2)<5$, a contradiction which completes the proof.