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

1.2k Views Asked by At

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$enter image description here

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?

1

There are 1 best solutions below

3
On 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: enter image description here

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.