Is there any known result on the maximum degree of faces in regular-and-planar graphs ? In particular, is anything known about maximum degree of the faces in a 4-regular planar graph? By degree of a face I mean the number of edges forming it.

  • $\begingroup$ About your definition of "degree": is an edge that is traversed twice on a face counted twice? $\endgroup$ Sep 11, 2012 at 20:18
  • $\begingroup$ Didn't think of that possibility. But for each face, each edge bounding it, need be counted only once. right ? Or am I missing something very obvious ? $\endgroup$
    – Arnab
    Sep 11, 2012 at 20:23
  • 6
    $\begingroup$ At least for $d=2,3,4$, there can be arbitrarily large faces. For $d=2$, take really long cycles. For $d=3,4$, it's easier to think in the dual form, i.e., triangulations and quadrangulations with arbitrarily high degree. For example, for $d=3$, take the cone of the wheel graphs. $\endgroup$ Sep 11, 2012 at 20:37
  • 3
    $\begingroup$ For d=3,4 it's easy enough to think in the primal, geometrically: d=3 may be given by a prism over an n-gon, d=4 by an antiprism. d=5 is also possible but doesn't have quite as simple a description (e.g. one way to do it is to take an icosahedron, choose two poles interior to opposite faces, cut it on a longitude line from pole to pole, and glue multiple copies together along their cut lines). $\endgroup$ Sep 11, 2012 at 23:36
  • 2
    $\begingroup$ It appears that you have crossposted this question simultaneously. Our site policy only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. Simultaneous crossposting duplicates effort and fractures discussion. I am voting to close; if your question is still not answered you may request reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites). $\endgroup$ Sep 12, 2012 at 0:26


Browse other questions tagged or ask your own question.