3-regular planar Graphs with 5 and 6 sided faces

549 Views Asked by At

I have the following question: For what number $n$ does there exist a 2-connected planar graph $G$ with $n$ vertices such that $G$ is 3-regular and every face of $G$ has degree either 5 or 6?

My progress so far: Let $a$ be the number of faces with degree 5, $b$ be the number of faces with degree 6, and $m$ be the number of edges. Then \begin{align*} &3n=2m&& a+b-m+n=2 && 2m=5a+6b. \end{align*} [...solving linear equation system...] Hence $a=12$, $n=20+2b$, and $m=30+3b$ and there could be a graph for any even $n\geq20$.

There exists such a graph with $b=0$ (the Ikosaeder), one for $b=2$, and one for $b=20$ (a football). However, I am quite certain that there is no such graph for $b=1$. The problem I see is that the equations above do not capture the 3-regularity of the graph.

Do you see any way to impose further restrictions on $n$ or a proof for which $n$ a graph exists?

1

There are 1 best solutions below

0
On BEST ANSWER

You are right that there is no such graph with $b=1$. I don't know of an easy way to show this, however. In fact such graphs exist for every other value of $b$, and the number of such graphs for each value of $b$ is given by this OEIS sequence.