+ \{p_k,p_1\}$ is a *cycle*, and $\abs{E(C)}$ is the *length* of $C$. We represent this cycle by the cyclic sequence of its vertices, for example $C = (p_1,p_2,\dotsc,p_k,p_1)$. If $G$ is a graph and $H\subseteq G$ is a path or cycle such that $V(H)=V(G)$, then $H$ is called *Hamiltonian*.

Rainbow Paths
=============

Introduction
------------

Consider the complete graph $K_n =(V,E)$ with a proper edge coloring $c\colon E \to {\mathbold{N}}$. Given this coloring, the rainbow paths and cycles are exactly the paths and cycles in $K_n$ that use every color at most once.

If $P$ is a rainbow path, then we will refer to the colors in $c(P)$ as *old* and to those in $c(P)^c=c(E)\setminus c(P)$ as *new*. Edges colored with old colors are *old*, edges colored with new colors are *new*.

In [@GyarfasMhalla2010], Gyárfás and Mhalla proved that regardless of how the coloring is chosen, there always are rainbow paths on at least $(2n+1)/3$ vertices. Now we give the basic idea behind their proof, the details of which we will see later. Consider any maximum rainbow path $P=(p_1,\dotsc,p_k)$ in $K_n$, and consider an edge $\{p_i,p_{i+1}\}$ such that $\{p_1,p_{i+1}\}$ is new, as in the following figure.

(-5.2,-1.5)(5.2,2) (-5,0)[.08]{}[p1]{} (0,0)[.08]{}[pi]{} (1,0)[.08]{}[psi]{} (5,0)[.08]{}[pt]{}

