The range of possible values for the length of a cycle in a 3-connected pentagulation

graph theoryplanar-graphs

Edits: Parcly Taxel first discovered that the length of cycle cannot be constrained by the 3-connected condition. However, I think
the construction proposed by kabenyuk later is wonderful. Therefore, I
choose it as the best answer. But this does not mean that Parcly
Taxel's construction is not excellent.

A pentagulation is a planar graph whose faces are all of length five; see the following Figure, for example.

enter image description here

My question is:

What is the range of possible values for the length of a cycle in a 3-connected pentagulation?

First, We can find some special values by making some specific observations. For example, $5$-cycles, $8$-cycles, $9$-cycles. But for any integer $i\ge 3$, does there always exist a 3-connected pentagulation that contains a cycle $C_i$?

Note that we can easily see that in any 3-connected planar graph, any two faces can share at most one edge. So the following cases will not occur.

enter image description here

Best Answer

Let us prove that for any integer $k\geq8$ there exists a 3-connected pentagulation with a cycle of length $k$.

First, how can we construct a 3-connected pentagulation with a large number of vertices. To do this, take the dodecahedral graph and put a new dodecahedral graph inside some face of it. This process can go on as long as you like.

Now consider three cases.

  1. Let $k=3s+2=4+3(s-2)+4$. Choose a sufficiently large 3-connected pentagulation and in it consider a chain of $s$ faces where each face has exactly one edge in common with its neighbor. The edges of this chain give a cycle of length $3s+2$.
  2. Let $k=3s$. Choose a chain of $s-1$ faces. Then add to the first face of this chain a face that has by one common edge with two adjacent faces of our chain.
  3. Let $k=3s+1$. If $s\geq5$, then it is similar to case 2. The cases $k=10$ and $k=13$ are special.

The figure illustrates the cases $k=20,21,22$. Inside each face there is the number of edges of that face included in the cycle.

enter image description here

Addendum.

I find it useful to give another universal reasoning.

  1. First note that the interior of a triangle can be divided into pentagons as shown in the figure.

enter image description here

Now let's inscribe in each of the three pentagons the dodecahedral graph. Let us call this graph $P$. The graph $P$ is a planar $3$-connected graph.

Another way to partition a triangle into pentagons can be found here (we will call it $Q$). For completeness, here is the $Q$ figure.

enter image description here

  1. Now let $C_k$ ($k\geq3$) be an arbitrary cycle whose vertices form a regular $k$-gon in the plane. Triangulate the interior and exterior of this cycle. Then in each triangle we inscribe graph $P$ or $Q$. The result is a $3$-connected pentagulation with cycle $C_k$.

Note of February 21. I corrected one inaccuracy in my answer.

One more remark. In point 1 it is actually enough to inscribe the dodecahedral graph into only two of the three pentagons, the result is a graph with $37$ vertices, which is isomorphic to the graph $Q$.

Related Question