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


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.

  • 1
    $\begingroup$ @Esha: Wow... perhaps you should have waited for a more interesting class of graphs before accepting my answer? $\endgroup$ – Niel de Beaudrap Oct 26 '10 at 10:33
  • $\begingroup$ I think your graph class can be generalized as 2 cycles attached to endpoints of a path. $\endgroup$ – Esha Oct 26 '10 at 10:46
  • $\begingroup$ Btw,does accepting your answer means I wont get any more intersting replies? $\endgroup$ – Esha Oct 26 '10 at 10:47
  • $\begingroup$ @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. $\endgroup$ – Niel de Beaudrap Oct 26 '10 at 10:58
  • $\begingroup$ @Esha: if you change your mind, you can change which answer is marked accepted. meta.stackexchange.com/questions/5234/… $\endgroup$ – András Salamon Oct 26 '10 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.