2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

enter image description here enter image description here

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.

$\endgroup$
  • $\begingroup$ hmm, can you draw your "contradiction"? $\endgroup$ – draks ... Aug 18 '13 at 21:06
  • $\begingroup$ Do you think it's possible to formalize your approach for larger graphs as well? $\endgroup$ – draks ... Aug 18 '13 at 21:07
  • $\begingroup$ 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? $\endgroup$ – Servaes Aug 18 '13 at 21:23
  • $\begingroup$ 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? $\endgroup$ – draks ... Aug 18 '13 at 21:35
  • $\begingroup$ I edited my answer to show some examples of 'close' counter-examples, and to include a proof for general $n$. $\endgroup$ – Servaes Aug 18 '13 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.