The graph $G$ below is a counterexample.

Construct $G$ as follows:

Letting $n$ be quite large, $V_1 = \{v_0,v_1,\ldots, v_{n+1}\}$ and $E_1= \{v_iv_{i+1}; i=0,\ldots, n\}$ as stated in the problem.

Let $k$ be an integer about $\frac{n}{3}$ and let $l=\frac{n}{2}$. So $2k=\frac{2n}{3}$ and $2k-l=\frac{n}{6}$.

Then $V \setminus V_1$ $=\{u_0,\ldots, u_{l-1},u_{l+1},\ldots, u_{2k-1},u_{2k+1} \ldots, u_{n}\}$. $= \{u_j; \ j \in \{0,\ldots, n\}\setminus \{l,2k\} \}$

Then the edges in $G \setminus E_1$ are:

(a) $v_0u_0$ and $u_0v_{l}$; $v_ku_k$ and $u_kv_{2k}$;

(b) $v_iu_i$ and $u_iv_{n+1}$ for $i=1,2,\ldots, l-1$;

(c) $v_mu_m$ and $u_mv_l$ for $m=n, n-1,n-2, \ldots, 2k+1,2k-1,\ldots, l+2$;

(d) $v_{2k}u_{l+1}$ and $u_{l+1}v_{l+1}$.

Here is a sketch of the proof that there is no path $P$ in $G$ starting at $v_0$ and ending at $v_{n+1}$ that is longer than $E_1$.

Claim 1: (i) Any path $P$ in $G$ not starting nor ending at any vertex in $V \setminus V_1$ can take only $O(1)$ of the vertices in $V \setminus V_1$. (ii) Any path $P$ of length at least $n-2$ from $v_0$ to $v_{n+1}$ must cover almost all of $V_1$ i.e., at most $O(1)$ vertices in $V_1$ are not in $P$.

To see (i) of Claim 1, note that every $u_j$ has degree 2 and so if a path $P$ contains $u_j$ and doesn't end at $u_j$ then $P$ must contain both edges incident to $u_j$. But every $u_j$ is adjacent to at least one of $v_l, v_k,v_{2k}$, or $v_{n+1}$.

So in light of (i) of Claim 1, if there is a path $P$ from $v_0$ to $v_{n+1}$ of length $\ell$ then $P$ must contain $\ell-O(1)$ vertices in $V_1$. If $\ell \ge n-O(1)$ then almost all of $V_1$ must be in $P$.

Claim 2: The longest path in $G' \doteq G \setminus \{v_k,v_{2k},v_{n+1}\}$ has length no larger than $\max\{n-2k + (2k-l), n-2k + (l-k)\}$ $=\max\{\frac{n}{3}+\frac{n}{6}, \frac{n}{3}+\frac{n}{6}\} = \frac{n}{2} $.

Indeed, the components of $G \setminus \{v_k,v_{2k},v_l,v_{n+1}\}$ [i.e., take the graph with the vertex $v_l$ removed from $G'$] are

$C_1= G[\{v_m; 2k<m<n+1 \}+\{u_m; 2k<m<n+1 \}]$;

$C_2=G[\{v_m; l<m<2k\}+\{u_m; l<m<2k\}]$; and

$C_3= G[\{v_m; k<m<l\} +\{u_m; k<m<l\}]$.

One of these components $C_1$ has no path of length greater than $n-2k=\frac{n}{3}$; $C_2$ has no path of length greater than $2k-l=\frac{n}{6}$ and $C_3$ has no path of length greater than $l-k=\frac{n}{6}$. So this means that the length of the longest path in
$G'$ is no more than the length of the longest path in $C_p$ plus the length of the longest path in $C_{p'}$ for some distinct $p, p' \in \{1,2,3\}$ where $C_1,C_2,C_3$ are as above. From this Claim 2 follows.

**Remainder Of The Proof:** So let $P$ be a path from $v_0$ to $v_{n+1}$, and let $e$ be the *first* edge in $P$ that is not in $E_1$. [Order the edges in $P$ from the starting point $v_0$ of $P$ to the finishing point $v_{n+1}$ of $P$.]

*Case 1: $e=v_ku_k$*. Then $e$ is the $k+1$-th edge in $P$, and the first $k$ edges of $P$ form the path $v_0v_1\ldots v_k$, and the $(k+2)$nd edge in $P$ is $u_kv_{2k}$. Thus as both $v_k$ and $v_{2k}$ are vertices that are in the first $k+2$ edges of $P$, the length of $P$ can be no more than $k+2$ plus the length of the longest path in $G' = G \setminus \{v_k,v_{2k},v_{n+1}\}$ plus 1.
Thus from Claim 2 $P$ can be no longer than $k+2+\frac{n}{2}+1=\frac{5n}{6}+3 < n$.

*Case 2: $e=v_{l+1}u_{l+1}$*. Then $e$ is the $(l+2)$nd edge in $P$ and the first $l+1$ edges of $P$ form the path $v_0v_1\ldots v_lv_{l+1}$, and the $(l+3)$rd edge in $P$ is $u_{l+1}v_{2k}$. So $v_{2k},v_l$ and $v_{l+1}$ are vertices that appear in the first $l+3$ edges of $P$. However, note that $G \setminus \{v_{2k},v_{l+1},v_{l}\}$ has more than one connected component, and furthermore,
every vertex in the set $V_{11}=\{v_{2k-1},v_{2k-2},\ldots, v_{l+2}\}$ in a different component from every vertex in the set $V_{12}=\{v_{2k+1},\ldots, v_{n}\}$. So the remaining edges of $P$ will miss at least either every vertex in $V_{11}$ or every vertex in $V_{12}$.
Furthermore, neither $V_{11}$ nor $V_{12}$ intersects the first $l+3$ edges of $P$, so either $P \cap V_{11}$ or $P \cap V_{12}$ must be empty.
As each of $V_{11}$ and $V_{12}$ have at least $\frac{n}{6}$ vertices, so this and Claim 1 implies that $P$ will not have length $n$.

*Case 3: $e=v_lu_m$ for some $m < 2k$*. Then $e$ is the $(l+1)$st edge in $P$ and the first $l+1$ edges of $P$ form the path $v_0v_1\ldots v_lu_m$ and the $(l+2)$nd edge in $P$ is $u_mv_{m}$. However, note that the only way $P$ can be extended to reach $v_{n+1}$ is if the rest of $P$ is $v_mv_{m+1}\ldots v_{n+1}$. [Indeed, note that $v_k$ and $v_{l}$, and $v_m$ are in the first $l+2$ edges in $P$, and so the remaining edges of $P$
are all (a) in a single component of $G \setminus \{v_k,v_l,v_m\}$ that has a vertex $v'$ adjacent to $v_m$ that isn't in the first $l+2$ edges of $P$, and (b) form a path starting at $v'$ and ending at $v_{n+1}$. The only such vertex $v'$ is $v_{m+1}$, and furthermore, one can see that the component of $G \setminus \{v_k,v_l,v_m\}$ containing $v_{m+1}$ is a tree, and so the path $v_{m+1} \ldots v_{n+1}$ is the only path from $v'=v_m$ to $v_{n+1}$ and so these must be the remaining edges of $P$.] As $m > l+2$ this implies that $P$ will not have length longer than that of $v_0v_1\ldots v_{n+1}$.

*Case 4: $e=v_lu_m$ for some $m > 2k$*. Can be finished in a similar fashion as Case 3.

*Case 5: $e=v_0u_0$ which is the first edge in $P$*. Then $v_0u_0$ is the first edge in $P$, and the 2nd edge in $P$ is $u_0v_l$. We divide into two subcases.

The first subcase of Case 5 is that the next vertex in $P \cap V_1$ after $v_l$ is in the set $\{v_m: m > l\}$. Then, by Claim 1 it follows that $P$ must contain almost every vertex in $\{v_i: i<l\}$ as well, and so as every path in $G \setminus \{v_{n+1}\}$ from $\{v_m: m > l\}$ and $\{v_i: i< l\}$ must pass through
$\{v_l,v_{2k}\}$, it follows that $P$ must enter back into $\{v_i: i< l\}$ via the edges $v_{2k}u_kv_k$, and then $P$ must cover almost every vertex in $\{v_i: i< l\}$. But this is impossible as every vertex in $\{v_i: k<i<l\}$ is in a different component of $G \setminus \{v_l,v_k,v_{n+1}\}$ from every vertex $\{v_i: 0<i<k\}$, so $P$ cannot be extended to cover vertices in both $\{v_i: k<i<l\}$ and $\{v_i: 0<i<k\}$. So $P$ cannot be extended from $v_k$ to cover vertices in both the sets $\{v_i: 0<i<k\}$.
$\{v_i: k<i<l\}$. Each of these sets has $\frac{n}{6}$ vertices. So by Claim 1 $P$ cannot have length $n$.

The 2nd subcase of Case 5 is that the next vertex in $P \cap V_1$ is in the set $\{v_i: i< l\}$. One can finish using the same line of reasoning as in the above subcase.

*Case 6: $e=v_iu_i$; $i=1,\ldots, l-1$; $i \not = k$. Then $e$ is the $i+1$-th edge in $P$, and the $i+2$th edge in $P$ is $u_iv_{n+1}$, which implies that $P$ has length $i+2 \le l+1 < n$.