# Smallest Planar Cubic Graph with Non Hamiltonian Edge

I'm looking for the smallest simple planar cubic hamiltonian graph without triangles and with at least one edge that never lies on a hamiltonian cycle.

I've got one with triangles $\phantom{somespaceneed}$ or one non planar example

It's obvious that the middle edge never lies on a Hamilton cycle, since If once you start down the [middle] dark path, forever will it dominate your destiny and you will never return to the origin without crossing one vertex twice. I'm not sure, if this approach (patching 2 blobs left and right of the non-HC edge) leads to the smallest solution.

May the Force be with you...

-

## 2 Answers

The following information may be useful in finding out what is known. I believe it was J. Bosak who first looked somewhat systematically at the question of when a graph which is planar, 3-valent and 3-connected has hamiltonian cirucits which used every edge or no edge of a graph. Edges on every HC were (not very usefully) referred to as a-edges and edges on no HC were called b-edges.

A discussion of a and b edges can be found here as well as the reference to Bosak's paper, Hamiltonian lines in cubic graphs.

https://cs.anu.edu.au/~bdm/papers/c4cp.pdf

-
Thanks for the "b-edge" keyword and the cool reference... –  draks ... Sep 3 '12 at 6:41

A b-edge is an edge which is on no hamiltonian cycle in a graph. Figure [B] shows the unique smallest 3-connected cubic planar graph which has a 6-edge (both (0,3) and (4,7) are b-edges)

-