9
$\begingroup$

The question about the existence of a cycle of a given length in a $3$-connected planar graph all faces of which are pentagonal, and also attempts to solve it led to the following problem.

Insert into triangle a planar graph with pentagonal faces only, so that the degree of each of its vertices is not less than three.

This problem was solved here. The solution is obtained as follows. Consider a plane graph with $7$ vertices:

enter image description here

Each face in it is a pentagon. We inscribe a dodecahedron graph into two of the three pentagons. As the result we obtain a graph with $37$ vertices all faces of which inside triangle are pentagons. The degree of each vertex of this graph is at least $3$. Denote this graph by $Q$. We can see a plane image of graph $Q$ here and here.

My question. Is graph $Q$ minimal in the number of vertices among planar graphs in which there is a single triangular face and all other faces are pentagons and the degree of each vertex of this graph is at least $3$?

This question is posed purely out of curiosity and because I could neither prove the minimality of $Q$, nor construct a smaller graph with this property.

Addendum.

The answers of Parcly Taxel and student91 show that $37$ was too rough estimate for graph with specified property. The graph constructed by Parcly Taxel is symmetric and especially beautiful. But I am itching to clarify my question.

Clarifying Question. After all, what is the minimal number of vertices in planar $3$-connected graphs all faces of which are pentagons except for exactly one triangular face.

As follows from Euler's formula for planar graphs, if a graph has a single triangular face and other faces are pentagons and three vertices are of degree $4$ and others are of degree $3$, then such graph must have $25$ vertices and Parcly Taxel constructed it.

$\endgroup$

2 Answers 2

13
$\begingroup$

Take the regular dodecahedron and open up the three faces around one vertex like petals of a flower. To each of the new degree-$2$ vertices attach a new edge and new vertex, then join these three latter new vertices by a triangle. The result is a $3$-connected partition of a triangle into $15$ pentagons using $25$ vertices.

This graph was found using the plantri command plantri_ad -F3_1^1F5F6 16 followed by a little processing in Sage.


To show that this pentangulation is minimal, note that the dual of a $13$-pentagon example (the number of pentagons must be odd by Euler's polyhedron formula) would be a pure triangulation minus $2$ edges to leave $13$ vertices of degree $5$ and one of degree $3$. Consider all possible ways of adding these two edges:

  • The extra edges are both incident to the degree-$3$ vertex. This leaves just degree-$5$ and $6$ vertices, and plantri_ad -F5F6 14 will find all such triangulations. But the only graph returned is the Kleetope of the hexagonal antiprism, where the degree-$6$ vertices have no mutual neighbour that can correspond to the triangle face in the dual.
  • One extra edge is incident, giving a degree-$4$ vertex and either of $\{6,6,6\}$ or $\{7,6\}$ (plantri_ad -F4_1^1F5F6F7 14) as the other non-degree-$5$ vertices before edge removal. There is only one graph in this class with $\{4,6,6,6\}$ as the "odd" vertex degrees, so the removed edges would have to form a perfect matching on these vertices. But the graph induced by the "odd" vertices has no perfect matching.
  • The extra edges solely connect degree-$5$ vertices and leave "odd" degrees as $\{6,6,6,6\}$ and $\{7,6,6\}$ (plantri_ad -F3_1^1F5F6F7 14). There is only one graph in this class with $\{7,6,6\}$ as the "odd" degrees; the degree-$7$ vertex has to be adjacent to both degree-$6$ vertices in order to correspond to a triangle pentagulation, which is unfortunately not the case here (the degree-$7$ is only adjacent to one of the degree-$6$s).

We can exclude the $11$- and $9$-pentagon examples similarly, the latter of which is the absolute minimum from considerations of the sum of degrees of the pentangulation's vertices. Thus the graph above constitutes a minimal pentangulation of the triangle.


Again in a similar fashion, we can show that this partition of a square into $14$ pentagons is minimal:

$\endgroup$
7
  • 1
    $\begingroup$ It's a beautiful graph. I would like to draw your attention to the fact that I clarified my question. $\endgroup$
    – kabenyuk
    Feb 22, 2023 at 16:01
  • 1
    $\begingroup$ @kabenyuk I just edited my answer to have a proof of minimality... $\endgroup$ Feb 22, 2023 at 16:02
  • $\begingroup$ Yes, I'm already trying to understand your reasoning. $\endgroup$
    – kabenyuk
    Feb 22, 2023 at 16:08
  • 2
    $\begingroup$ so unfortunate I can only give one upvote $\endgroup$
    – student91
    Feb 22, 2023 at 16:40
  • 1
    $\begingroup$ @student91 you can give bounties to reward existing answers though. $\endgroup$ Feb 23, 2023 at 0:57
5
$\begingroup$

If you look at the following image:

Image of Parcly Taxel

That I retrieved from this answer, you see the left graph has a pentagonal envelope and a hexagonal interior and 31 vertices. The second graph has a hexagonal envelope and a triangle in the middle. When we put this second graph inside the hexagon of the first, we obtain a graph that you desire with only 34 vertices.

You should turn it "inside out" such that the pentagonal envelope becomes a center face and the triangle becomes the envelope if you want a triangle partition.

$\endgroup$

You must log in to answer this question.

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