is a maximum rainbow path, then adding any edge from $E(p_k,V(P)^c)$ to it cannot result in a rainbow path (otherwise $P$ would not be maximum). This means that all edges in $E(p_k,V(P)^c)$ use colors that are also used by $P$. The same argument can be made for edges in $E(p_1,V(P)^c)$.

\[prop:maximality\] If $P=(p_1,\dotsc,p_k)$ is a maximum rainbow path with respect to some coloring $c$, then $c(p_1,V(P)^c)\subseteq c(P)$ and $c(p_k,V(P)^c)\subseteq c(P)$.

In particular, $\abs{A(P)} = \abs{{\Gamma_{\mathrm{new}}(p_1,P)}} \geq n-k$ and $\abs{B(P)} = \abs{{\Gamma_{\mathrm{new}}(p_k,P)}} \geq n-k$.

Using this simple observation, we directly obtain the following lower bound on the length of a maximum rainbow path.

\[prop:n/2-bound\] In every proper edge coloring of $K_n$, there are rainbow paths on at least $(n+1)/2$ vertices.

Consider an arbitrary proper edge coloring $c$ of $K_n$, and let $P = (p_1,\dotsc,p_k)$ be a maximum rainbow path in this coloring. We have $$\abs{c(p_k,V(P)^c)} = \abs{V(P)^c} = n-k\text,$$ and $$\abs{c(P)} = \abs{E(P)} = k-1\text.$$

By Proposition \[prop:maximality\], we have $c(p_k,V(P)^c)\subseteq c(P)$, and hence $\abs{c(p_k,V(P)^c)} \leq \abs{c(P)}$. Thus $n-k \leq k-1$, and so we have $$k \geq \frac{n+1}{2}\text,$$ as claimed.

Actually, we proved something slightly stronger, namely, that given any vertex $v$ of $K_n$, there is a rainbow path on $(n+1)/2$ 