of $P$, it does give us more flexibility; as we will see we can now often simply ‘forget’ about constant terms. This is the main idea behind the upcoming proof that in every proper edge coloring of $K_n$, there are rainbow paths of length $(3/4-o(1))n$.

Now for some definitions. For any vertex $v\in V$, we define the *new neighborhood* of $v$ relative to a rainbow path $P$ by $${\Gamma_{\mathrm{new}}(v,P)} = \{ u \in V\setminus \{v\} : c(u,v) {\not\in}c(P) \}\text.$$ Analogously, if $C$ is a rainbow cycle, then $${\Gamma_{\mathrm{new}}(v,C)} = \{u \in V\setminus \{v\} : c(u,v) {\not\in}c(C) \}\text.$$

Moreover, for any rainbow path $P=(p_1,\dotsc,p_k)$, we define the sets $$\begin{aligned}
 &A(P) = \{ p_i \in V(P) : p_{i+1}\in {\Gamma_{\mathrm{new}}(p_1,P)}\}\\
\shortintertext{and}
&B(P) = \{ p_i \in V(P) : p_{i-1}\in {\Gamma_{\mathrm{new}}(p_{k},P)}\}\text. \end{aligned}$$ Note that these definitions are symmetric in the sense that if $P'=(p_k,\dotsc,p_1)$, then $A(P)=B(P')$ and $A(P') = B(P)$. Figure \[fig:a\] serves as a visual aid for the formal definitions of $A(P)$ and $B(P)$.

(-5.2,-2)(5.2,2) (-5,0)[.08]{}[p1]{} (-3,0)[.08]{}[x]{} (-2,0)[.08]{}[y]{} (0,0)[.08]{}[pi]{} (1,0)[.08]{}[psi]{} (2,0)[.08]{}[u]{} (3,0)[.08]{}[v]{} (5,0)[.08]{}[pk]{}

(-4.25,0)[a]{} (-3.75,0)[b]{}

(-1.25,0)[a1]{} (-.75,0)[b1]{}

(3.75,0)[a2]{} (4.25,0)[b2]{}

(-3,0)[.25]{} (0,0)[.25]{} (2.75,-.25)(3.25,.25)

We will be working mostly with maximum rainbow paths, that is, rainbow paths of maximum length. Clearly, if $P = (p_1,\dotsc,p_k)$ 