# Existence of a cubic planar graph with one hexagonal face and four square faces.

I'm currently playing around with Euler's Formula and found the following for cubic planar graphs: $$\sum_{k=1}^F f_k = 6F-12,$$ where $f_k$ is the degree of the $k$th face. I tried to apply this formula on graphs without triangles. The smallest example I found is:

$\hskip2.5in$

where $\sum_1^6 4=24=6\cdot 6 -12$. Adding one more face gives $30$ and now I'm trying for several hours (CPU time) to draw a graph $G$ with six faces of degree $4$ and one with $6$. An example $G'$ with five of degree $4$ and two of $5$ was right at hand, by extending the central square and the outer face to a pentagon.

$G'$ and $G$ both have (or should have) $F=7,\; E=15$ and $V=10$ due to Euler's formula. $G$ further is bipartite since it has only even degree faces. This means that the set of vertices splits into two sets of $5$ vertices.

Is it impossible to draw such a graph, and if so: Why?

Let $$G$$ be a cubic planar graph with one hexagonal face and four square faces. By Euler's formula $$V-E+F=2,$$ where $$F=7$$ and $$E=\tfrac32V$$, and hence $$V=10$$. Let $$G_1$$ and $$G_2$$ be the induced subgraphs on the vertices of the hexagonal face, and on the remaining $$4$$ vertices respectively. Without loss of generality $$G_2$$ lies inside the hexagon $$G_1$$. Because $$G$$ is cubic there are precisely $$6$$ edges going out from $$G_1$$, hence going into $$G_2$$. It follows that there are precisely $$3$$ edges in $$G_2$$. As $$G$$ does not contain triangular faces $$G_2$$ is either a claw or a path.

If $$G_2$$ is a claw then each of the three leaves is adjacent to two vertices in $$G_1$$. Then removing the root of the claw from $$G$$ we can smooth out the remaining three leaves of $$G_2$$ to get a new planar graph on the vertices of $$G_1$$. Because $$G$$ is triangle-free this smoothing out produces three distinct edges that are not edges of $$G_1$$. But there is no such planar graph, a contradiction.

If $$G_2$$ is a path then contracting the edges adjacent to the terminal vertices yields two vertices that are each adjacent to three distinct vertices of $$G_1$$. As this graph is planar, it is the following graph:

Because $$G$$ is triangle-free the two terminal vertices of $$G_2$$ are adjacent to non-adjacent vertices in $$G_1$$, i.e. to the vertices on the left and right in the picture. Then the two middle vertices of $$G_2$$ are adjacent to the top and bottom vertices of $$G_1$$ in the picture. This is impossible as $$G$$ is planar.

Ths shows that there is no cubic planar graph with one hexagonal face and four square faces.

• hmm, can you draw your "contradiction"? Aug 18, 2013 at 21:06
• Do you think it's possible to formalize your approach for larger graphs as well? Aug 18, 2013 at 21:07
• I got that you're trying to construct a contradiction, it's just that all the graphs I draw (now after your answer) contain also for example two hexagons next to some triangles. If you know the counter-example that is "closest" (a subjective measure) I would be interested to see it. Concerning the larger graphs, I would just move ahead with 8,9,10,... faces. Any idea how to formalize your idea for that? Aug 18, 2013 at 21:35