<p>How about this one?</p>
<p><a href="https://i.sstatic.net/6RG47.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/6RG47.png" alt="" /></a><br />
<sub>(source: <a href="http://yaroslavvb.com/upload/save/cstheory-circulant-graph.png" rel="nofollow noreferrer">yaroslavvb.com</a>)</sub></p>
<p><b>Update</b>:
Here are some if you restrict attention to connected 3-regular bridgeless graphs, from Mathematica's <code>GraphData</code> database</p>
<p><a href="https://i.sstatic.net/F6lTD.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/F6lTD.png" alt="" /></a><br />
<sub>(source: <a href="http://yaroslavvb.com/upload/save/cstheory-noham2.png" rel="nofollow noreferrer">yaroslavvb.com</a>)</sub></p>
<ul>
<li><a href="http://mathworld.wolfram.com/DoubleStarSnark.html" rel="nofollow noreferrer">http://mathworld.wolfram.com/DoubleStarSnark.html</a>
<li><a href="http://mathworld.wolfram.com/SzekeresSnark.html" rel="nofollow noreferrer">http://mathworld.wolfram.com/SzekeresSnark.html</a>
<li><a href="http://mathworld.wolfram.com/TuttesGraph.html" rel="nofollow noreferrer">http://mathworld.wolfram.com/TuttesGraph.html</a>
<li><a href="http://mathworld.wolfram.com/ZamfirescuGraphs.html" rel="nofollow noreferrer">http://mathworld.wolfram.com/ZamfirescuGraphs.html</a>
</ul>
<pre><code>graphs = GraphData[{&quot;Cubic&quot;, &quot;Connected&quot;, &quot;Bridgeless&quot;}];
noham = Select[graphs, GraphData[#, &quot;HamiltonianPathCount&quot;] == 0 &amp;]
</code></pre>
<p><b>Another update</b>
Looks like <code>HamiltonianPathCount=0</code> doesn't always mean there's no Hamiltonian path, following Hamiltonian paths can be easily found</p>
<p><a href="https://i.sstatic.net/bTbX7.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/bTbX7.png" alt="" /></a><br />
<sub>(source: <a href="http://yaroslavvb.com/upload/save/cstheory-hampath.png" rel="nofollow noreferrer">yaroslavvb.com</a>)</sub></p>
<p>For the other two graphs, I didn't find any counter-examples with 1000 random greedy searches.</p>

CC BY-SA 2.5
2011-01-09T00:12:22.057Z
That is not even connected. Its two K_{4}'s
N27
CC BY-SA 2.5
2011-01-09T00:58:05.350Z
But it is bridgeless (obviously not what you were looking for though).
Andrew D. King
CC BY-SA 2.5
2011-01-09T02:00:07.627Z
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
CC BY-SA 2.5
2011-01-09T02:04:45.707Z
By the way does anybody know why mathworld has "Hamiltonian path count ?" in Zamfirescu graphs? It should have 0 I guess   (http://mathworld.wolfram.com/ZamfirescuGraphs.html)
N27
CC BY-SA 2.5
2011-01-09T02:32:00.693Z
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 
CC BY-SA 4.0
2011-01-09T00:04:25.710Z
2019-02-20T08:35:15.893Z
2020-06-17T09:38:08.363Z
Yaroslav Bulatov
<p>I believe there are <a href="http://tzamfirescu.tricube.de/TZamfirescu-077.pdf" rel="nofollow">as shown in this article</a>, though it seems non-trivial to discover one.</p>

CC BY-SA 2.5
2011-01-08T23:06:58.523Z
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
CC BY-SA 2.5
2011-01-08T23:15:31.527Z
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
CC BY-SA 2.5
2011-01-09T00:32:08.100Z
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
CC BY-SA 2.5
2011-01-08T21:35:43.407Z
2011-01-08T21:35:43.407Z
Gautam Kamath
<p>See <a href="https://cstheory.stackexchange.com/questions/3024/upper-bounds-on-the-length-of-longest-simple-path-in-non-hamiltonian-graph/3026#3026">this answer to an earlier question</a> for a bridgeless cubic graph in which the longest path is only polylogarithmically long.</p>

CC BY-SA 2.5
2011-01-10T16:57:19.363Z
2011-01-10T16:57:19.363Z
2017-04-13T12:32:28.167Z
David Eppstein
<p>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</p>

CC BY-SA 2.5
2011-01-10T08:46:08.377Z
@Hsien-Chih Chang 張顯之, yes I made mistake.
Saeed
CC BY-SA 2.5
2011-01-10T08:49:40.037Z
@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 張顯之
<graph-theory><co.combinatorics><hamiltonian-paths>
Cubic graphs and hamiltonian paths
N27
# Cubic graphs and hamiltonian paths

(Asked by: username_0 on 2011-01-08)

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

**Tags:** graph-theory, co.combinatorics, hamiltonian-paths

> **Comments:**
> **username_1**: @username_2, yes I made mistake.  
> **username_2**: @username_1: That's OK, maybe later you'll find a construction with fewer nodes than the one in the paper shown by @Gautam :)  

---

## 3 answers

### Answer by username_7 on 2011-01-10. Score: 9 | Accepted answer

See [this answer to an earlier question](https://cstheory.stackexchange.com/questions/3024/upper-bounds-on-the-length-of-longest-simple-path-in-non-hamiltonian-graph/3026#3026) for a bridgeless cubic graph in which the longest path is only polylogarithmically long.


---

### Answer by username_3 on 2011-01-09. Score: 3

How about this one?

(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)

http://mathworld.wolfram.com/DoubleStarSnark.html
http://mathworld.wolfram.com/SzekeresSnark.html
http://mathworld.wolfram.com/TuttesGraph.html
http://mathworld.wolfram.com/ZamfirescuGraphs.html

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.

> **Comments:**
> **username_0**: That is not even connected. Its two K_{4}'s  
> **username_4**: But it is bridgeless (obviously not what you were looking for though).  
> **username_0**: 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  
> **username_0**: By the way does anybody know why mathworld has "Hamiltonian path count ?" in Zamfirescu graphs? It should have 0 I guess   (http://mathworld.wolfram.com/ZamfirescuGraphs.html)  
> **username_5**: 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.  

---

### Answer by username_6 on 2011-01-08. Score: 3

I believe there are [as shown in this article](http://tzamfirescu.tricube.de/TZamfirescu-077.pdf), though it seems non-trivial to discover one.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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  
> **username_6**: 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.  

---

