will tacitly assume that increasing functions of $n$ dominate any constant. We are given a proper edge coloring $c$ of $K_n$. Then we denote by $t$ the number of vertices in a maximum length rainbow path, that is, there are no rainbow paths of length $t$ (on $t+1$ vertices).

We will assume throughout that we have $$t \leq \left(\frac{3}{4}-\epsilon\right)n\text,$$ trying to arrive at a contradiction.

During the proof, let $a$ be a ‘large enough’ constant. For example $a = 100+\ceil{100/\epsilon}$ is more than enough.

### Nice rainbow paths

For any rainbow path $P$, we define the set $$R(P) = \{ r\in V(P)^c : \abs{{\Gamma_{\mathrm{new}}(r,P)} \cap V(P)^c} > a\}  \text.$$ So $R(P)$ is the set of vertices in $V(P)^c$ that have more than $a$ new neighbors in $V(P)^c$. Then we have the following definition.

A *nice* rainbow path is a rainbow path $P$ satisfying $$\abs{R(P)}> n-t- 1/\epsilon\text.$$

In other words, nice rainbow paths are such that all but at most $1/\epsilon$ vertices in $V(P)^c$ have more than $a$ new neighbors in $V(P)^c$. We will be interested in nice maximum rainbow paths, that is, nice rainbow paths on $t$ vertices. Before showing that such paths exist, we will motivate them by proving 