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 for which no two faces of odd length 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$ This graph is not necesary simple? That is two vertices can be connected with more than 1 edge? $\endgroup$ – Aqua Dec 29 '18 at 16:55
  • $\begingroup$ This would make a face of length 2, I think, which I ruled out. $\endgroup$ – Finallysignedup Dec 30 '18 at 5:04

Infinite counter examples of this form (just keep adding two more squares):

The key is to have a face with even degree incident to only one face with odd degree. Here's another way to achieve this goal.

Consider any cubic polyhedron $P$, which has a face, $f$, of odd degree.

Chamfer $P$ once to get $P'$. $P'$ is still cubic, and any face originally in $P$ is now only incident to hexagons.

Now, chamfer $P'$ to get $P''$. Here, every face incident to $f$ will be a hexagon, which is incident to hexagons on every other edge. Thus you can subdivide any edge in $f$ to get your desired kind of graph.

  • $\begingroup$ Thanks. I realize now I only wish to allow odd faces that are triangles (the rest even). I've posted this as a new question. $\endgroup$ – Finallysignedup Dec 30 '18 at 5:02

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.