1
$\begingroup$

Show that there is no regular planar graph (all vertices degree 3) so that all regions, including the unbounded region, are hexagonal.

I am sure this has something to do with the fact that for planar graphs the sum of degrees of regions is twice the number of edges. Looking for a hint to push me in the right direction.

$\endgroup$
4
  • 1
    $\begingroup$ The Euler characteristic of a planar graph is $2$. However, if every face is hexagonal and every vertex has degree $3$, $V+F-E$ cannot be $2$. $\endgroup$ Commented Mar 15, 2017 at 3:00
  • $\begingroup$ (1) 3v = 2e (why?); (2) 2f = 6e (why?); (3) express v,f in terms of e; (4) v-e+f = 2 yields an easy contradiction. $\endgroup$
    – quasi
    Commented Mar 15, 2017 at 3:02
  • $\begingroup$ @quasi: I did it in terms of $f$ but it is the same thing. There are $6$ vertices on every face and every vertex belongs to $3$ faces, hence $v=2f$. Every face has six edges and every edge belongs to two faces, hence $e=3f$. $\endgroup$ Commented Mar 15, 2017 at 3:07
  • $\begingroup$ @Jack D'Aurizio: Your version is an ounce or two simpler, but I agree, in essence, they're the same. $\endgroup$
    – quasi
    Commented Mar 15, 2017 at 3:12

1 Answer 1

5
$\begingroup$

The Euler characteristic of a planar graph is $2$. However, if every face is hexagonal and every vertex has degree $3$, $V+F-E$ cannot be $2$, because it is $ 2F+F-3F = 0$.

Explanation: there are $6$ vertices on every face and every vertex belongs to $3$ faces, hence $V=2F$. Every face has six edges and every edge belongs to two faces, hence $E=3F$.

However, we have such kind of graph embedded in a torus (courtesy of R. M.):

$\hspace{3.5cm}$enter image description here

$\endgroup$

You must log in to answer this question.

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