1
$\begingroup$

Direct question:

Is it possible to construct a finite, planar, $k$-regular graph in which all the faces except one have the same degree (are bounded by a cycle with the same number of edges), and the remaining face (the external face, if you like) has a distinct degree? If not, why not? If so, what is an example of such a graph?

Context:

I'm teaching a course in combinatorics this fall and, as the University describes graph theory being part of the curriculum, I brushed up on some and incorporated a fellow prof's notes on basic graph theory for part of the semester. The Platonic solids are a nice basic example, so we did that proof.

So, in defining a platonic graph, one says that such a graph is planar and regular, and all faces have the same degree. I thought that a student might misclassify a graph as platonic if the external face had a different degree, and set about trying to draw such an example. This proving difficult, I started thinking that it can't be done. I invited the students to prove it as a project, and moved on. My attempts to produce such a graph systematically showed me how to do it with an infinite graph -- take a pentagon and extend squares off to infinity, e.g. -- or with two faces of different, equal degree -- a prism on any polygon. And these suggest a route of proof, but I'm not steeped in enough graph theory at the moment to come up with it. The previous prof couldn't work out a proof on short notice either. This isn't unexpectedly hard, is it? I'd like to be able to give my students a conclusion on this before we end the unit.

$\endgroup$
3
  • 2
    $\begingroup$ You get quite a bit of constraints from Euler formula $v-e+f=2$: your graph is regular, i.e. $2e=vk$, and the $f-1$ faces are $\ell$-gonal, while the remaining face is $\ell'$-gonal. So this gives $2e=(f-1)\ell+\ell'$. Finally, don't forget topology, which forbids $\ell$ greater than 5... $\endgroup$ Oct 11, 2013 at 15:50
  • $\begingroup$ Yes, there is a 1-dimensional family of numerical solutions for $(k,\ell)=(3,3),(3,4),(3,5),(4,3),(5,3)$ and that's all. They can considered separately for whether they are realizable as graphs. $\endgroup$ Oct 11, 2013 at 23:48
  • $\begingroup$ The case $(3,3)$ doesn't work since $\ell'<e$. $\endgroup$ Oct 11, 2013 at 23:54

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.