get $$\abs{{\Gamma_{\mathrm{new}}(v,P)} \cap R(P)} > a-1/\epsilon\text,$$ and hence $$\abs{{\Gamma_{\mathrm{new}}(v,P)} \cap R(P) \setminus V(Q_i)} > a- 1/\epsilon -k\text.$$ Now the claim follows from $$a-1/\epsilon -k \geq k + \abs{F}\text,$$ which holds because $k \leq (a-\abs{F}-1/\epsilon)/2$.

The importance of this fact comes from the following lemma.

\[lemma:no-paths\] If $P$ is a nice maximum rainbow path, then every rainbow path $$Q = (q_1,\dotsc,q_k)$$ satisfies at least one of the following properties:

1.  $V(Q)\not\subseteq V(P)$,

2.  $({\Gamma_{\mathrm{new}}(q_1,Q)}\cup {\Gamma_{\mathrm{new}}(q_k,Q)}) \cap R(P)= \emptyset$,

3.  $\abs{c(Q)\setminus c(P)}> 2$, or

4.  $k< t-a/3$.

Suppose that there is a rainbow path $Q=(q_1,\dotsc,q_k)$ satisfying none of the properties (P1–4).

Because (P2) is violated, either ${\Gamma_{\mathrm{new}}(q_1,Q)}\cap R(P)\neq \emptyset$ or ${\Gamma_{\mathrm{new}}(q_k,Q)}\cap R(P)\neq \emptyset$. In any case, there is an endpoint $q$ of $Q$ such that for some vertex $s_1\in R(P)$, we have $c(q,s_1){\not\in}c(Q)$. Then let $$F = \{c(q,s_1)\}\cup (c(Q)\setminus c(P))\text,$$ and since (P3) is violated, we have $\abs{F}\leq 3$.

By Proposition \[prop:long-paths\], we know that the subgraph induced by $R(P)$ contains a rainbow path $S = (s_1,\dotsc,s_l)$ with $l\geq \floor{(a-3-1/\epsilon)/2}$ such that $c(S)\cap (F\cup c(P)) = \emptyset$. So $S$ does not use any colors in $$F\cup c(P) = \{c(q,s_1)\}\cup c(Q)\cup c(P)\text,$$ and hence the path $S' = (q_1,s_1,\dotsc,s_l)$ is a rainbow path 