Hamiltonian path between two specific nodes

Question

We have a simple undirected connected graph G and two specific nodes s and t. We delete a node and gets to a graph G' that it has a hamiltonian path between s and t. What necessary conditions has to be that we can say the main graph G has a hamiltonian path between s and t too?

For example, take the Petersen graph, shown below:

We have this path between e and f nodes: "eabcdigjhf".

And if we delete node d we have this path: "eabchjgif"

Answer 1

As a partial (negative) result, the problem of finding a Hamiltonian $s,t$-path in $G$ is NP-complete, even if we are given a Hamiltonian $s,t$-path in $G'$.

(The usual proof in such cases that finding a structure is the same as checking it exists doesn't seem to work, since there's no way to easily use an algorithm for the decision problem to figure out which edges of the Hamiltonian $s,t$-path in $G'$ are necessary.)

---

To see prove this, we will assume that we have an efficient algorithm that extends a Hamiltonian $s,t$-path in $G'$ to a Hamiltonian $s,t$-path in $G$. Then, we will use it to find Hamiltonian paths in arbitrary graphs.

Let $H$ be any $n$-vertex graph with designated vertices $s$ and $t$, in which we want to find a Hamiltonian $s,t$-path. First, add a vertex $s'$ that must always go right after $s$: replace all edges $sv$ by edges $s'v$, and add an edge $ss'$. Call the resulting graph $H_1$.

Next, we will turn $H_1$ into a graph $H_2$ that's guaranteed to have a Hamiltonian $s,t$-path. To do this, add $n$ extra vertices $v_1, \dots, v_n$ that are adjacent to each vertex of $H_1$, and to each other. To get a Hamiltonian $s,t$-path in $H_2$, just alternate vertices of $H_1$ and vertices from $v_1, \dots, v_n$ in an arbitrary way.

Finally, add the following vertices one at a time, using our putative algorithm to check extend our existing Hamiltonian $s,t$-path if it is possible:

1. A vertex adjacent only to $s$ and $v_1$.
2. A vertex adjacent only to $v_1$ and $v_2$.
3. A vertex adjacent only to $v_2$ and $v_3$.
4. And so on, up until a vertex adjacent only to $v_{n-1}$ and $v_n$.
5. A vertex adjacent only to $v_n$ and $s'$.

These additions are essentially equivalent to declaring, one at a time, that we are forced to use the edges $sv_1, v_1v_2, \dots, v_{n-1}v_n$, $v_ns'$.

If $H_1$ had a Hamiltonian $s,t$-path (which must contain the edge $ss'$) then $H_2$ has a path which uses all of these edges, and therefore at every step of the procedure above, we will keep finding a Hamiltonian path. Conversely, if we do find a Hamiltonian path that uses all these edges, then replacing these edges by the edge $ss'$ gives us a Hamiltonian path in $H_1$.

Therefore our algorithm will find a Hamiltonian $s,t$-path in $H_1$ - and then in $H$, which was arbitrary.