<p>The idea of the constructions in this answer are from Niel de Beaudrap's answer.</p>
<p>Assume that <span class="math-container">$H$</span> is an arbitrary graph with a unique Hamiltonian path between <span class="math-container">$v_l$</span> and <span class="math-container">$v_r$</span>.</p>
<h3>Construction I.</h3>
<p>Assume that <span class="math-container">$G_l$</span> is a graph, and <span class="math-container">$U_l \subseteq V(G_l)$</span> s.t. there are exactly 2 Hamiltonian paths starting from vertices in <span class="math-container">$U_l$</span>. Similarly for <span class="math-container">$G_r$</span>. Attach <span class="math-container">$G_l$</span> to <span class="math-container">$H$</span> by adding edges between <span class="math-container">$v_l$</span> and vertices in <span class="math-container">$U_l$</span>. Similarly attach <span class="math-container">$G_r$</span> to <span class="math-container">$H$</span> using <span class="math-container">$v_r$</span>. The resulting graph has the required property.</p>
<h3>Construction II.</h3>
<p>Assume that there is no other Hamiltonian path in <span class="math-container">$H$</span> starting from <span class="math-container">$v_l$</span>, and that <span class="math-container">$G$</span> is a graph, and there are exactly 4 Hamiltonian paths starting from vertices in <span class="math-container">$U \subseteq V(G)$</span>. Attach <span class="math-container">$G$</span> to <span class="math-container">$H$</span> by adding edges between the vertices in <span class="math-container">$U$</span> and <span class="math-container">$v_l$</span>. The resulting graph has the required property.</p>
<p>An example for <span class="math-container">$G$</span> in the second construction is a <span class="math-container">$C_{4}$</span>, taking two non-adjacent vertices as <span class="math-container">$U$</span>.</p>

CC BY-SA 2.5
2010-10-26T11:34:56.173Z
2010-10-26T12:06:36.677Z
2020-06-17T09:38:08.363Z
Kaveh
<p>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</p>

<blockquote>
  <p>A<sub>1</sub>&nbsp;&ndash;&nbsp;P<sub>0</sub>&nbsp;&ndash;&nbsp;A<sub>2</sub>&nbsp;&ndash;&nbsp;...&nbsp;&ndash;&nbsp;A<sub>h&minus;1</sub>&nbsp;&ndash;&nbsp;A<sub>1</sub></p>
</blockquote>

<p>and</p>

<blockquote>
  <p>B<sub>1</sub>&nbsp;&ndash;&nbsp;P<sub>n</sub>&nbsp;&ndash;&nbsp;B<sub>2</sub>&nbsp;&ndash;&nbsp;...&nbsp;&ndash;&nbsp;B<sub>k&minus;1</sub>&nbsp;&ndash;&nbsp;B<sub>1</sub>&nbsp;,</p>
</blockquote>

<p>connected by the path</p>

<blockquote>
  <p>P<sub>0</sub>&nbsp;&ndash;&nbsp;P<sub>1</sub>&nbsp;&ndash;&nbsp;...&nbsp;&ndash;&nbsp;P<sub>n</sub>&nbsp;,</p>
</blockquote>

<p>then there are Hamiltonian paths between each vertex pair {A<sub>a</sub>&nbsp;,&nbsp;B<sub>b</sub>} for a,b&nbsp;&isin;&nbsp;{1,2} but for no others.</p>

CC BY-SA 2.5
2010-10-26T10:33:37.443Z
@Esha: Wow... perhaps you should have waited for a more interesting class of graphs before accepting my answer?
Niel de Beaudrap
CC BY-SA 2.5
2010-10-26T10:46:00.380Z
I think your graph class can be generalized as 2 cycles attached to endpoints of a path.
Esha
CC BY-SA 2.5
2010-10-26T10:47:35.760Z
Btw,does accepting your answer means I wont get any more intersting replies?
Esha
CC BY-SA 2.5
2010-10-26T10:58:46.127Z
@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
CC BY-SA 2.5
2010-10-26T12:42:59.420Z
@Esha: if you change your mind, you can change which answer is marked accepted.  http://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work/5235#5235
András Salamon
CC BY-SA 2.5
2010-10-26T10:09:27.527Z
2010-10-26T12:53:25.293Z
2010-10-26T12:53:25.293Z
Niel de Beaudrap
<p>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]</p>

CC BY-SA 2.5
2010-10-26T09:27:01.473Z
"All Hamilton-connected graphs are Hamiltonian." (see: http://mathworld.wolfram.com/Hamilton-ConnectedGraph.html). So, you need not say that the graph neither admits any Hamiltonian cycle, nor is Hamiltonian-connected (the latter is redundant).
Sadeq Dousti
<graph-theory><co.combinatorics>
Non-hamiltonian Graphs with unique hamiltonian path between exactly 4 pair of vertices
Esha
# Non-hamiltonian Graphs with unique hamiltonian path between exactly 4 pair of vertices

(Asked by: username_0 on 2010-10-26)

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 username_1 for pointing it out]

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

> **Comments:**
> **username_1**: "All Hamilton-connected graphs are Hamiltonian." (see: http://mathworld.wolfram.com/Hamilton-ConnectedGraph.html). So, you need not say that the graph neither admits any Hamiltonian cycle, nor is Hamiltonian-connected (the latter is redundant).  

---

## 2 answers

### Answer by username_2 on 2010-10-26. Score: 5 | Accepted answer

The idea of the constructions in this answer are from username_3'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$.


---

### Answer by username_3 on 2010-10-26. Score: 5

Here's a trivial example class [and now, also generalized slightly in view of username_0'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.

> **Comments:**
> **username_3**: @username_0: Wow... perhaps you should have waited for a more interesting class of graphs before accepting my answer?  
> **username_0**: I think your graph class can be generalized as 2 cycles attached to endpoints of a path.  
> **username_0**: Btw,does accepting your answer means I wont get any more intersting replies?  
> **username_3**: @username_0: 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.  
> **username_4**: @username_0: if you change your mind, you can change which answer is marked accepted.  http://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work/5235#5235  

---

