Are there conditions (e.g., bridgeless) under which a connected, regular, trivalent planar graph contains either a face whose boundary has length two or a face whose boundary has odd length? Since googling does not yield any results, nor does playing with the handshaking Lemma and the Euler formula, I suspect the general statement must be false. However, I cannot construct a counter example.

Many thanks!

Edit: I do not see how the first comment below applies here.

  • $\begingroup$ See math.stackexchange.com/questions/105278/… $\endgroup$ – Misha Lavrov Oct 20 '18 at 17:56
  • $\begingroup$ What is a bigon? $\endgroup$ – William Elliot Oct 20 '18 at 22:24
  • $\begingroup$ @WilliamElliot A "bigon" is a face of length 2 (that is, a pair of parallel edges). So that part of the conditions can be skipped if we're thinking of simple graphs. (The other weird terminology in the question is "trivalent", which is the same as "cubic" or "3-regular".) $\endgroup$ – Misha Lavrov Oct 20 '18 at 23:41
  • $\begingroup$ @MishaLavrov I don't see how the linked question applies here. $\endgroup$ – Finallysignedup Oct 21 '18 at 11:24
  • $\begingroup$ @Finallysignedup It tells you that counterexamples exist with $4n$ vertices for all $n\ge 3$ (actually, $n=2$ also works) but not for $10$ vertices. (For a planar graph, being bipartite is equivalent to having no odd faces.) $\endgroup$ – Misha Lavrov Oct 21 '18 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.