# Non-hamiltonian Graphs with unique hamiltonian path 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 Hamiltonian paths between exactly 4 pair of vertices. I have identified one such group of graphs. Would like to see more such examples.[Redundant information deleted; thanks to Sadeq Dousti for pointing it out]

The idea of the constructions in this answer are from Niel de Beaudrap's answer.

Assume that $H$ is an arbitrary graph with a unique Hamiltonian path between $v_l$ and $v_r$.

### Construction I.

Assume that $G_l$ is a graph, and $U_l \subseteq V(G_l)$ s.t. there are exactly 2 Hamiltonian paths starting from vertices in $U_l$. Similarly for $G_r$. Attach $G_l$ to $H$ by adding edges between $v_l$ and vertices in $U_l$. Similarly attach $G_r$ to $H$ using $v_r$. The resulting graph has the required property.

### Construction II.

Assume that there is no other Hamiltonian path in $H$ starting from $v_l$, and that $G$ is a graph, and there are exactly 4 Hamiltonian paths starting from vertices in $U \subseteq V(G)$. Attach $G$ to $H$ by adding edges between the vertices in $U$ and $v_l$. The resulting graph has the required property.

An example for $G$ in the second construction is a $C_{4}$, taking two non-adjacent vertices as $U$.

Here's a trivial example class [and now, also generalized slightly in view of Esha's comment]: graphs G(h,k,n) constructed from a path of length n, by adjoining a cycle of length h and a cycle of length k to the two ends. If the two cycles are

A1 – P0 – A2 – ... – Ah−1 – A1

and

B1 – Pn – B2 – ... – Bk−1 – B1 ,

connected by the path

P0 – P1 – ... – Pn ,

then there are Hamiltonian paths between each vertex pair {Aa , Bb} for a,b ∈ {1,2} but for no others.

• @Esha: Wow... perhaps you should have waited for a more interesting class of graphs before accepting my answer? – Niel de Beaudrap Oct 26 '10 at 10:33
• I think your graph class can be generalized as 2 cycles attached to endpoints of a path. – Esha Oct 26 '10 at 10:46
• Btw,does accepting your answer means I wont get any more intersting replies? – Esha Oct 26 '10 at 10:47
• @Esha: You're right about the cycles: I'll generalize my answer to include this. Also: I would certainly imagine that accepting my answer will have a negative impact on the number of people who look into the question. – Niel de Beaudrap Oct 26 '10 at 10:58
• @Esha: if you change your mind, you can change which answer is marked accepted. meta.stackexchange.com/questions/5234/… – András Salamon Oct 26 '10 at 12:42