Return to Answer

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 Zachary in a comment.

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 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 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$.
It seems to me that this can be proved along the same lines as Smith's theorem.

However, this method 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.
So 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 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 Zachary in a comment.

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 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.
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.

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$.
It seems to me that this can be proved along the same lines as Smith's theorem.

However, this method 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.
So 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 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$.
It seems to me that this can be proved along the same lines as Smith's theorem.

However, this method 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.
So 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.