3
$\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$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ hmm, can you draw your "contradiction"? $\endgroup$
    – draks ...
    Aug 18, 2013 at 21:06
  • $\begingroup$ Do you think it's possible to formalize your approach for larger graphs as well? $\endgroup$
    – draks ...
    Aug 18, 2013 at 21:07
  • $\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, 2013 at 21:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .