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$
  • 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$ – Jack D'Aurizio Mar 15 '17 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 Mar 15 '17 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$ – Jack D'Aurizio Mar 15 '17 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 Mar 15 '17 at 3:12
4
$\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$

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.