Let G be a connected, planar graph for which every vertex has degree 3, except that one vertex has degree 2.

Is it possible to construct an example of such G whose only odd faces are triangles, and for which no two such triangles share a common vertex?

(For my purposes I may assume there are no faces of length 1 or 2, in which case there must be an odd face of length at least 3. By the handshake lemma, there are an even number of, hence at least 2, such odd faces.)

  • $\begingroup$ For my own edification.. what is an odd face ? $\endgroup$ – T. Fo Dec 30 '18 at 5:04
  • $\begingroup$ Face with odd number of sides. $\endgroup$ – Zachary Hunter Dec 30 '18 at 5:09
  • $\begingroup$ I think "those bounded by an odd length cycle" is a sensible definition. $\endgroup$ – Finallysignedup Dec 30 '18 at 5:11

Here is one such graph - or, more precisely, one such plane embedding of a graph, since the lengths of the faces are not properties of the graph itself. It has two faces of length 3 (including the external face), two faces of length 4, and two faces of length 6.

enter image description here

(Motivation: we start with a triangular pyramid, which has all the required properties except for the degree-2 vertex, and modify it a little to make it work.)

  • $\begingroup$ Thanks. I now wish to only have degree 3 vertices. I've made a new (hopefully final) question. $\endgroup$ – Finallysignedup Dec 30 '18 at 6:03

Take two cycles of the same order 2n+1, $C_a$ and $C_b$ and number each in clockwise fashion.

"Glue together" $v_{1a}$ and $v_{1b}$, and then do the same for $v_{2a}$ and $v_{2b}$, so that there is just one edge between $v_1$ and $v_2$.

Then, for each $i > 2$ create an edge between $v_{ia}$ and $v_{ib}$.

Finally, subdivide the edge between $v_1$ and $v_2$.

  • $\begingroup$ Thanks. Sorry that I could not tick both answers. $\endgroup$ – Finallysignedup Dec 30 '18 at 6:02
  • $\begingroup$ Understandable, it is the fault of my laziness in creating diagrams. $\endgroup$ – Zachary Hunter Dec 30 '18 at 6:04

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.