A conjecture on longest paths in a bipartite+path graph

Question

Conjecture: Let $G$ be a connected simple graph with minimun degree $3$. Suppose that for vertices $s$ and $t$ and a simple $(s,t)$-path $P$, $G \backslash E(P)$ is bipartite with stable classes of vertices $V(P)$ and $V(G)-V(P)$. Then $P$ is not a longest simple $(s,t)$-path of $G$.

Answer 1

Let's relax your question as follows: Suppose that the minimum degree requirement is only 2, and for the interior vertices of $P$ it is 3. Also, $P$ needn't be induced, so let's only suppose that $V\setminus P$ is stable. I claim that even with these conditions, it is hard to give an example where $P$ is a longest $(s,t)$-path.

Why? Because if the degree of every interior vertex of $P$ is odd, and the degree of the other vertices is even, then we can use Thomason's generalization of the Smith network theorem, according to which there are an even number of Hamiltonian-cycles through any edge of a graph where every degree is odd. To use the theorem, we first get rid of the vertices outside $P$; even degree ($2d$) vertices can be replaced by $d$ edges among $d$ arbitrary endpoints (OK, we should pay attention not to create multiple edges, but let's not care about the details).

Example 1. Suppose that $P=(s,a,b,t)$ and the vertices outside $P$ are $c$ and $d$ such that $c$ is connected to $s$ and $b$, while $d$ is connected to $a$ and $t$. Then after getting rid of the vertices outside $P$, we add the edges $sb$ and $at$ to the graph induced by $P$, so our new graph becomes a complete graph on $(s,a,b,t)$, minus the $st$ edge. By Smith's theorem, there is another Hamiltonian-path connecting $s$ and $t$, namely, $(s,b,a,t)$. In the original graph, this gives the path $(s,c,b,a,d,t)$, which is longer than $P$. (Note that this new path is not necessarily Hamiltonian in the original graph, only in our example because it was too small.)

For other degree distributions, we can also replace, say, a degree $3$ vertex outside $P$ with a triangle, and if the new Hamiltonian cycle would use two edges of it, we instead use only one, which doesn't make the path shorter, as the vertex outside $P$ will also be on it in the original graph. Thus eventually, we run into the problem of constructing uniquely Hamiltonian graphs with some extra conditions, which is not an easy problem.

Example 2. Suppose that $P=(s,a,b,c,d,t)$ and the vertices outside $P$ are $e$ and $f$ such that $d$ is connected to $s,b$ and $t$, while $e$ is connected to $a,c$ and $t$. Then after getting rid of the vertices outside $P$, we add the edges $sb,bd,sd$ and $ac,ct,at$ to the graph induced by $P$. Now we cannot use any parity argument, but we get a minimum degree $3$ graph (if we include the $st$ edge), so these typically are not uniquely Hamiltonian, namely, $(s,b,a,c,d,t)$ is another Hamiltonian path. In the original graph, this gives the path $(s,e,b,a,f,c,d,t)$. Here we were lucky that only one edge of each triangle was used. To see another example, let's consider another Hamiltonian path, $(s,b,d,c,a,t)$. Here $sb$ and $bd$ both would go through $e$, so instead, we will use the $sd$ edge, i.e., $(s,e,d)$ in the original graph, and similarly $ca$ and $at$ will give $(c,f,t)$. Thus, in the original graph our (non-Hamiltonian) path becomes $(s,e,d,c,f,t)$. (Unfortunately this is not even longer than $P$, just equally long, because all new edges were derived from the triangle trick.)