1
$\begingroup$

Yet another question I was going over and struggled.

Given a 3-regular connected planar graph, so that every vertex lies on the edge of a face of length 4, of a face of length 6 and of a face of length 8. Find the number of vertices, edges and faces of each length.

Obviously, in order to solve it one will have to use:

$n-e+f=2$

$2e=3n$

$2e=4f_4+6f_6+8f_8$

$f=f_4+f_6+f_8$

But using just these three equations doesn't lead to any useful result. The best I managed to get out of them is:

$f_4=6+f_8$

And some identities connection the edges to number of vertices to number of faces - none enough to solve the question. It seems as if I miss some identity that lies with the fact that "each vertex lies on the edge of a face of length 4, of a face of length 6 and of a face of length 8" - it can't be that the number of each of these faces is equal, they seem to be certainly different actually. Yet $f_6$ disappears along the way and I don't know how to go on. Any help/direction/ideas will be extremely helpful!

$\endgroup$
1
$\begingroup$

Consider the edges incident to some vertex $v$. Exactly two of these three edges border a face of length $4$. Therefore two thirds of all edges lie on the border of a face of length $4$. Hence $f_4=\frac{1}{4}\left(\frac{2}{3}\right)e=\frac{1}{6}e$. Using the same justification, we have $f_6=\frac{1}{6}\left(\frac{2}{3}\right)e=\frac{1}{9}e$, and $f_8=\frac{1}{8}\left(\frac{2}{3}\right)e=\frac{1}{12}e$.

Hence we have $$f=f_4+f_6+f_8=e\left(\frac{1}{6}+\frac{1}{9}+\frac{1}{12}\right)=\frac{13}{36}e.$$

Plugging this into our first equations, we have $$2=n-e+f=\frac{2}{3}e-e+\frac{13}{36}e=\frac{e}{36}.$$

Hence $e=72$, and plugging things back in, we get $n=\frac{2}{3}e=48$, $f=\frac{13}{36}e=26$, $f_4=\frac{1}{6}e=12$, $f_6=\frac{1}{9}e=8$, and $f_8=\frac{1}{12}e=6$.

$\endgroup$
  • $\begingroup$ Much simpler than I thought, thank you very much! $\endgroup$ – Studentmath Jun 28 '14 at 21:53
  • $\begingroup$ Even simpler(?): Count vertex-face incidences to find $n=4f_4=6f_6=8f_8$ $\endgroup$ – Hagen von Eitzen Jun 29 '14 at 9:01

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.