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.