Is every path with this property shorter than another path with the same endpoints? Suppose that $G=(V,E)$ is a simple graph and $P=(V_1,E_1)$ is a path in $G$ where 
$$V_1=\{v_0,v_1,\cdots,v_n\},\ E_1=\{v_0v_1,v_1v_2,\cdots,v_{n-1}v_n\}.$$
I found that if the path $P$ satisfies:
For any $v_i\in V_1$, there exist $v_j\in V_1\setminus \{v_i\}$ and $u\in V\setminus V_1$ such that $uv_i,uv_j\in E$.
Then you can always find a longer $v_0$-$v_n$ path in $G$.
I have tried to find a counterexample to this for a long time but still cannot find one. So I think maybe the above conjecture is true. Is it true or is there any known result about this? Any ideas are welcome!
 A: A very natural special case is the following:
For any $v_i\in V_1$, there exists exactly one $v_j\in V_1\setminus \{v_i\}$ such that there is a $u\in V\setminus V_1$ such that $uv_i,uv_j\in E$.
This means that all $u\in V\setminus V_1$ have degree two.
In this case we can show that a longer $v_0v_n$ path exists as follows.
Proof: Define the graph $G'$ by replacing each length-two path $v_iuv_j$ with an edge $v_iv_j$, and also add $v_0v_n$.
(This might possibly give a multigraph, but that won't be a problem, and even if it were, we could reduce it to the case when $G'$ is a simple graph with a simple case analysis.)
$G'$ is a 3-regular graph and $v_0,..,v_n$ is a Hamiltonian-cycle in it.
By Smith's theorem, there is another Hamiltonian cycle in $G'$ which contains the edge $v_nv_0$.
This necessarily gives a longer $v_0v_n$ path in the original graph $G$, finishing the proof. $\square$
The more general case is when any $v_i\in V_1$ has exactly one neighbor $u\in V\setminus V_1$ (whose degree, $deg(u)$, might be more than two) can also be transformed into a cubic graph $G'$ by converting each $u$ into a cycle of length $deg(u)$, whose vertices are each connected to one neighbor of $u$ in $G$.
Then we would need to use a generalization of Smith's theorem that given a cycle $v_0,..,v_n$ in a cubic graph, we can find another cycle covering $v_0,..,v_n$ and containing the edge $v_nv_0$.
I conjectured that this was also true, but a counterexample was given by Martin and by Zachary in the comments, see below.
This method also fails when some $v_i$ can have more than one neighbor from $V\setminus V_1$.
In this case if one of $v_i$'s neighbors, $u$, has $deg(u)>2$, then we could simply delete the $uv_i$ edge from $G$.
Also if $deg(u)=2$, and $u$'s other neighbor is some $v_j$ that also has another neighbor from $V\setminus V_1$, then we could delete $u$ from $G$ without violating the conditions.
But the issue is if some $v_i$ is connected to several degree-two vertices from $V\setminus V_1$, whose other neighbors from $V_1$ have degree three.
Maybe this will help in finding a counterexample, or a proof.
A: [Update: Now testing paths where $u$ can connect any number of $v$'s.]
Here is some Mathematica code to test the conjecture, which reports that it is true for $n\le7$.
n = 7;
jumpy[x_] := Min[Rest[x] - Most[x]] > 1
noncons = Select[Subsets[Range[n + 1] - 1, {2, Floor[n/2] + 1}], jumpy]
enough[setup_] := Length[Union[Flatten[setup]]] > n
noexcessl[setup_] := Or[Length[Last[setup]] == 2, Not[Or @@ 
    Table[enough[Delete[setup, {-1, i}]], {i, Length[Last[setup]]}]]]
easy = {___, {___, a_, ___, b_, ___}, ___, {___, c_, ___ ,d_, ___}, ___} /; 
      Or[And[c == a + 1, d == b + 1], And[c == a - 1, d == b - 1]]
setups0 = Select[Subsets[noncons, n - 1], enough];
setups0 // Length
setups1 = Select[setups0, noexcess];
setups1 // Length
setups2 = Select[setups1, And[nointer[#], noexcessl[#], ! MatchQ[#, easy]] &];
setups2 // Length
setups2 // Last

A setup in this code is a list of the $v$'s connected by each $u$, e.g. $$\{\{1, 7\}, \{2, 7\}, \{3, 7\}, \{4, 6\}, \{5, 7\}, \{0, 4, 7\}\}$$
We restrict to set ups where

*

*the $u$'s connect only non-consecutive $v$'s (since the conjecture holds trivially for any path with consecutive $v$'s connected by some $u$)

*all $v$'s are connected to some $u$ ($\tt{enough}$)

*every $u$ is needed to connect some $v$ ($\tt{noexcess}$)

*no pair of $v$'s is connected by more than one $u$ ($\tt{nointer}$); no $v$ can be disconnected from a $u$ while retaining a legitimate setup ($\tt{noexcessl}$); and no pair of the form $\{a,b\}$ has a counterpart of form $\{a+1,b+1\}$ which would make finding a path easy ($\tt{easy}$).

For $n=7$, we find respectively $4692858$, $16632$ and $332$ setups to consider after these last three bulletpoints.
paths0 = Prepend[0] /@ Append[n] /@ Permutations[Range[n - 1], n - 1];
jumpsin[path_] := Select[Sort /@ Partition[path, 2, 1], jumpy]
paths = Select[paths0, Length[#] + Length[jumpsin[#]] > n + 1 &]
covered[jumps_, setup_] := Outer[Complement[#1, #2] === {} &, jumps, setup, 1] // Boole
good[mat_] := And[Min[Plus @@ Transpose[mat]] == 1, Max[Plus @@ mat] == 1]
solutions[setup_] := Select[paths, good[covered[jumpsin[#], setup]] &]
solutions[setups2 // Last]
shortpaths = jumpsin /@ paths;
solcount[setup_] := Count[shortpaths, jumps_ /; good[covered[jumps, setup]]]
Min[solcount /@ setups2]

For each set up, we consider paths from $v_0$ to $v_n$ which are longer than the original path. We construct a matrix ($\mathtt{covered}$) whose rows are the jumps in the path, and whose columns are the $u$'s in the setup, recording whether each jump is covered by that $u$. Then we check ($\mathtt{good}$) that:

*

*the minimum row-sum checks that every jump in the path goes via some $u$ in the setup

*the maximum column-sum checks that each $u$ is used at most once.

So, for instance, the setup above works with the path
$$\{0, 1, 2, 3, 4, 6, 5, 7\}$$
which is also abbreviated by its jumps
$$\{\{4,6\},\{5,7\}\}$$
We find that all setups for $n\le 7$ work with at least $1$ path.
This enumeration of setups was too memory-intensive to work readily for higher $n$, but a variant looking for setups with $n=8$ and at most $5$ $u$'s turned up the following interesting case: The setup
$$\{\{0,5\}, \{1,4,7\}, \{2,6\}, \{3,8\}\}$$
has some longer paths than the original, but none hit every vertex of the original path.
A: Disclaimer: this is not a proof but rather some ideas which may or may not help.
If we identify the pairs $v_i, v_j$ such that there's $u$ with $v_iuv_j \in E$ with a segment $[i, j]$, we are going to have at least $\frac{n+1}{2}$ segments.
Now we can argue similarly to the Vitali covering lemma. We have a collection of segments, covering $1, \ldots, n$ (let's assume we count starting from $1$ rather then from $0$). We can find two families of segments $\{ I \}$ and $\{ J \}$ such that


*

*Segments in each family are either disjoint or nested

*There are disjoint subfamilies $\tilde I$ and $\tilde J$ such that each segment intersect at most two neighbouring.


Now at least one of the families has measure at least $\frac{n+1}{2}$. Assume wlog that 
$$
| \cup I_j | \geq | \cup J_j | 
$$
If we order the segments in $\tilde I$ and $\tilde J$ so that $J_k$ intersects exactly two neighbours say $I_{l-1}$ and $I_{l}$ and $|J_k \cap I_{l-1}| + |J_k \cap I_{l}| = |J_k|$, then it would suffice to walk trough the nested segments in $I_{l-1}$, then "jump" using $J_k$ to $I_l$ and walk through the nested family in $I_l$.
The scheme above assumes that all $u$'s are distinct.
