is such that $c(p_i,p_{i+1})\in c(p_k,V(P)^c)$. Then there is a vertex $v\in V(P)^c$ such that $c(p_k,v)=c(p_i,p_{i+1}){\not\in}c(\rho_i\cdot P)$. Since $\rho_i\cdot P$ ends in $p_k$ and $v{\not\in}V(P) = V(\rho_i\cdot P)$, the rainbow path $\rho_i\cdot P$ violates Proposition \[prop:maximality\].

The second part follows by symmetry.

This fact was used by by Gyárfás and Mhalla to find rainbow paths on $(2n+1)/3$ vertices. Because the proof is quite elegant and uses a technique similar to those used later on, we give it here.

\[thm:gm2010\] In every proper edge coloring of $K_n$, there is a rainbow path on at least $(2n+1)/3$ vertices.

Consider an arbitrary proper edge coloring $c$ of $K_n$, and let $P = (p_1,\dotsc,p_k)$ be a maximum rainbow path with respect to $c$. By Proposition \[prop:maximality\], $c(p_k,V(P)^c)\subseteq c(P)$. Now let $$X = \{ c(p_i,p_{i+1}) : p_i\in A(P) \}\text.$$ Then we have $\abs{X} = \abs{A(P)} \geq n-k$. Since $X\subseteq c(P)$, we get $$X\cup c(p_k,V(P)^c)\subseteq c(P)\text,$$ and hence $\abs{X \cup c(p_k,V(P)^c)} \leq \abs{c(P)} = \abs{E(P)} = k-1$. By Proposition \[prop:maximality-rot\], we have $\abs{X \cap c(p_k,V(P)^c)} = \emptyset$, and thus $$\abs{X\cup c(p_k,V(P)^c)} = \abs{X} + \abs{c(p_k,V(P)^c)} \geq n-k + n-k\text,$$ and so $2n - 2k\leq k-1$, or $$k \geq \frac{2n+1}{3}\text,$$ which is what we needed to prove.

Now 