I started drawing planar, cubic, bipartite graphs consisting of faces with $4$ or $6$ vertices only. I found that six $4$-faces are sufficient to do that. The smallest graph is a planar drawing of the cube.

How many vertices or $6$-faces are necessary to get two non-isomorphic graphs?

  • $\begingroup$ Your question is a little confusing. Are you asking for the smallest (in terms of vertices) pair of planar cubic graphs with 6-sided faces? $\endgroup$ – gilleain Jul 20 '15 at 12:49
  • $\begingroup$ @gilleain yes; 6 4-sided and x 6-sided faces... $\endgroup$ – draks ... Jul 20 '15 at 14:17

Since the outer face must have length 4 or 6, it should be possible to prove your graphs must be at least 3-connected. But then your graphs are examples of Barnette graphs (cubic bipartite 3-connected planar graphs) which are conjectured to all have Hamiltonian cycles.

These have been studied fairly extensively, and you can find a drawings of all the Barnette graphs on up to 20 vertices in Appendix A here. Browsing through that appendix, it seems there is exactly 1 of your graphs on 8, 12, 14, 16, and 18 vertices (0, 2, 3, 4, and 5 6-faces), no such graph on 10 vertices, and there are 3 non-isomorphic such graphs on 20 vertices (20-3, 20-5, and 20-8 in the Appendix).


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.