# Graphs having unique hamiltonian paths between exactly 4 pair of vertices

Need some example graphs which are not hamiltonian, i.e, does not admit any hamiltonian cycle, but which have hamiltonian path. It has unique hamiltonian paths between exactly 4 pair of vertices. I have identified one such group of graphs. Would like to see more such examples.

-
Why do you need more examples? How'bout the graph with five vertices formed by joining two triangles at one corner? In fact, start with two triangles join them together by a string of edges, and attach to a vertex along the line a complete graph on some number of vertices, voila, infinitely many examples. – Willie Wong Oct 26 '10 at 16:02
The first one is not only for triangles, it actually generalizes to a family of graphs and that is exactly the class I have in mind. I would like to see more such "graph families".. preferably construction to generate this kind of graphs. About your next example, I am not very clear. How can you attach a clique at some point on the path between the two triangles? that will form a local loop instead of beoing covered by HP. – Esha Oct 27 '10 at 4:50

This answer elaborates on Willie Wong's comment and also provides another class of examples. Start with a clique $K_n$, pick two vertices $u, v \in K_n$, and glue two triangles onto $K_n$ at $u$ and $v$. It is easy to see that for any $n$, this graph is not Hamiltonian but there do exist exactly four pairs of vertices that are the endpoints of a Hamiltonian path. Furthermore, instead of using $K_n$, any subgraph such that there exists a Hamiltonian path between the distinguished vertices $u$ and $v$ will still do the trick.
Sorry, forgot to mention. It has to have unique hamiltonian paths between exactly 4 pair of vertices. Also, tthe triangles can be generalized as $C_m$ for some $m$ – Esha Oct 28 '10 at 2:59