# Draw a cubic planar graph with six faces of degree $4$ and one with $6$…

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 six faces of degree $4$ and one face of degree $6$. As every edge bounds precisely two faces, $G$ has a total of $$\frac{6\cdot4+1\cdot 6}{2}=15,$$ edges. As $G$ is cubic, the number of edges is also precisely $\tfrac{3}{2}$ times the number of vertices, so $G$ has a total of $\tfrac{2}{3}\cdot15=10$ vertices. This also follows from the fact that the Euler characteristic of a connected planar graph equals $2$, and $G$ has $7$ faces.

The face of degree $6$ is bounded by a hexagon, containing $6$ vertices. As $G$ is cubic, each of these vertices is adjacent to precisely one edge not bounding the face of degree $6$. As there are only $10$ vertices, at least two such edges are adjacent to the same vertex, hence bounding a triangle, i.e. a face of degree $3$, a contradiction.

EDIT: In response to the comments below, I have expanded my answer.

The question of which graph is 'closest' is not a well-defined one, but continuing the construction described above, one might find graphs like the following

But this is a matter of taste.

For any $n\geq1$, the non-existence of a planar cubic graph $G$ with $n$ faces of degree $4$ and one face of degree $n$ is proven in a similar fashion:

As before, the graph must have $\tfrac{5}{2}n$ edges and $\tfrac{5}{3}n$ vertices, already yielding a contradiction if $6\nmid n$. From the $n$ vertices of the $n$-gon bounding the face of degree $n$, there are $n$ edges going out to the remaining $\tfrac{2}{3}n$ vertices. Hence at least two of these edges are adjacent to the same vertex, bounding a face of degree $3$, a contradiction.

• hmm, can you draw your "contradiction"? – draks ... Aug 18 '13 at 21:06
• Do you think it's possible to formalize your approach for larger graphs as well? – draks ... Aug 18 '13 at 21:07
• We conclude that the graph must have a face of degree $3$, but we are given that it has only faces of degrees $4$ and $6$. This is a contradiction. What kinds of larger graphs do you have in mind? – Servaes Aug 18 '13 at 21:23
• 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? – draks ... Aug 18 '13 at 21:35
• I edited my answer to show some examples of 'close' counter-examples, and to include a proof for general $n$. – Servaes Aug 18 '13 at 22:14