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?
Best Answer
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.