5
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Related if not Duplicate. $\endgroup$
    – Kurt G.
    Commented May 18, 2022 at 13:35
  • 1
    $\begingroup$ @John I think it would be appropriate if you moved your comment to your question. Otherwise it looks like the question will be closed. $\endgroup$
    – kabenyuk
    Commented May 18, 2022 at 14:33
  • $\begingroup$ Try to find the number of faces, then the sizes of the faces. Can you conclude from that ? $\endgroup$
    – caduk
    Commented May 18, 2022 at 14:43
  • 2
    $\begingroup$ It seems to me that the question is of general interest. I voted to reopen the question. $\endgroup$
    – kabenyuk
    Commented May 18, 2022 at 16:14
  • 1
    $\begingroup$ You should find that the graph is almost completely triangulated, apart from one face. So if this graph exist, it has a unique embedding. We see by trying to construct it that it cannot exist. This solution is probably not very satisfactory, but this is the best I have for now... $\endgroup$
    – caduk
    Commented May 19, 2022 at 8:19

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ "This creates 8 new vertices alternating degree 2 and 3" The fact that these 8 vertices are different, and they are also different from the vertices of the 4-sided face, is not an easy problem. $\endgroup$
    – kabenyuk
    Commented May 19, 2022 at 14:34
  • $\begingroup$ In the article you mentioned it is proved that there is no regular planar graph of degree 5 on 14 vertices (Theorem 4). It would be nice if you could briefly state this proof. $\endgroup$
    – kabenyuk
    Commented May 19, 2022 at 14:39
  • $\begingroup$ @kabenyuk I described how to get an unambiguous construction of the triangulation. The proof of the paper seems to do something similar, though it's hard to follow, I will try to understand it more deeply later... $\endgroup$
    – caduk
    Commented May 19, 2022 at 23:50
1
$\begingroup$

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):

enter image description here

  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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .