# Cubic graphs and hamiltonian paths

I would like to ask, if anybody knows, whether there exists a 3-regular bridgeless graph which does not have a hamiltonian path (not necessarily extended to a hamiltonian circuit). Thank you

• @Hsien-Chih Chang 張顯之, yes I made mistake. – Saeed Jan 10 '11 at 8:46
• @Saeed: That's OK, maybe later you'll find a construction with fewer nodes than the one in the paper shown by @Gautam :) – Hsien-Chih Chang 張顯之 Jan 10 '11 at 8:49

See this answer to an earlier question for a bridgeless cubic graph in which the longest path is only polylogarithmically long.

I believe there are as shown in this article, though it seems non-trivial to discover one.

• Thank you very much for your reply Hoonose. However, I did not express my question very well: When I refer to hamiltonian paths, I am referring to at least one simple path of |V| vertices between some pair of vertices of the graph, not necessarily between each pair of nodes. So, there may exist nodes not connected with a simple path of length |V|. For example in figure 3 of your reference, there exists a simple path that connects a pair of nodes, but not each pair of nodes. You are actually referring to "hamiltonian connected" graphs. – N27 Jan 8 '11 at 23:06
• So let me please rephrase it: Is there a cubic bridgeless graph which does not have a simple path of |V| nodes? Even complex big graphs serving as counterexamples to relevant conjectures, such as the Grinberg (|V|=42) and Horton (|V|=96) have at least one such path – N27 Jan 8 '11 at 23:15
• The first section of the document I linked to talks about a "Small cubic 3-connected planar graph that is not traceable", where a graph if traceable if it has a Hamiltonian path. So the first graph they show there is cubic, doesn't have any bridges, is connected, but has no Hamiltonian path. I believe this is what you desire. The second part, homogeneously traceable, refers to a Hamiltonian path between every pair, and is probably not what you are looking for. – Gautam Kamath Jan 9 '11 at 0:32

(source: yaroslavvb.com)

Update: Here are some if you restrict attention to connected 3-regular bridgeless graphs, from Mathematica's GraphData database

(source: yaroslavvb.com)

graphs = GraphData[{"Cubic", "Connected", "Bridgeless"}];
noham = Select[graphs, GraphData[#, "HamiltonianPathCount"] == 0 &]


Another update Looks like HamiltonianPathCount=0 doesn't always mean there's no Hamiltonian path, following Hamiltonian paths can be easily found

(source: yaroslavvb.com)

For the other two graphs, I didn't find any counter-examples with 1000 random greedy searches.

• That is not even connected. Its two K_{4}'s – N27 Jan 9 '11 at 0:12
• But it is bridgeless (obviously not what you were looking for though). – Andrew D. King Jan 9 '11 at 0:58
• DoubleStarSnark and TuttesGraph have simple paths of length |V|. ZamfirescuGraph36 does not seem to have (I tried it 2-3 times). I needed only one counterexample so I did not try Szekeres. Thank you very much – N27 Jan 9 '11 at 2:00
• By the way does anybody know why mathworld has "Hamiltonian path count ?" in Zamfirescu graphs? It should have 0 I guess (mathworld.wolfram.com/ZamfirescuGraphs.html) – N27 Jan 9 '11 at 2:04
• Presumably nobody bothered to count the Hamiltonian paths in the Zamfirescu graphs. I don't know whether anybody has bothered to point out that Hamiltonian 3-regular graphs are automatically 3-edge colorable, so snarks are a good place to look for 3-regular graphs without Hamiltonian paths. – Peter Shor Jan 9 '11 at 2:32