\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1.46}{21(1)}{2014}

\usepackage{epsfig}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{latexsym}
\usepackage{graphicx}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\newtheorem{theor}{Theorem}[section]
\newtheorem{theo}[theor]{Theorem}
\newtheorem{propo}[theor]{Proposition}
\newtheorem{corol}[theor]{Corollary}
\newtheorem{lemma}[theor]{Lemma}
\newtheorem{definition}{Definition}[section]
\usepackage{hhline}

%\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}



% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

%\date{\dateline{}{J}\\
%\small Mathematics Subject Classifications: 05C15, 05C38}


\title{\bf Rainbow path and color degree in edge colored graphs}

\author{Anita Das \qquad  S. V. Subrahmanya \qquad P. Suresh\\
\small E-Comm Research Lab\\[-0.8ex]
\small Education \& Research, Infosys Limited\\[-0.8ex] 
\small Bangalore, India\\
\small\tt (anita\_das01, subrahmanyasv, suresh\_p01)@infosys.com \\
}


\date{\dateline{Oct 1, 2013}{Feb 12, 2014}{Feb 28, 2014}\\
\small Mathematics Subject Classifications: 05C15, 05C38}


\begin{document}




\maketitle






\begin{abstract}
Let $G$ be an edge colored graph. A {\it}{rainbow path} in $G$ is a path in
which all the edges are colored with distinct colors.   Let $d^c(v)$ be the color degree of a vertex $v$ in $G$, 
i.e. the number of distinct colors present on the edges incident on the vertex $v$. Let $t$
be the maximum length of a rainbow path in $G$.  
Chen and Li (2005) showed that  
 if $d^c \geq k$ ($k \geq 8$), for every vertex $v$ of $G$, then $t \geq \left \lceil \frac{3 k}{5}\right \rceil + 1$.
%(Long heterochromatic paths in edge-colored graphs, The Electronic Journal of Combinatorics 12 (2005), \#  R33, Pages:1-33.)
Unfortunately, the proof by Chen and Li is very long and comes to about 23 pages in the journal version.
Chen and Li states in their paper that it was conjectured by Akira Saito, that $t \ge \left \lceil \frac {2k} {3} \right \rceil$.
They also state in their paper that they believe $t \ge k - c$ for some constant $c$. 
 
In this note, we give a  short proof  to show that $t \ge \left \lceil \frac{3 k}{5}\right \rceil$, using
an entirely different method. Our proof is only
about 2 pages long. The draw-back is that our bound is less by 1, than the bound given by Chen and Li. 
We hope that the new approach adopted in this paper would eventually lead to the settlement of the conjectures by
Saito and/or Chen and Li. 
\vspace{.4cm}

\noindent{\bf Keywords:} edge colored graphs; rainbow path; color degree.
\end{abstract}


\section{Introduction}

Given a graph $G = (V, E)$, a map $c : E \rightarrow N$ ($N$ is the
set of non-negative integers) is called an {\it edge coloring} of
$G$. A graph G with  such a coloring $c$  is called
an {\it edge colored} graph. We denote the color of an edge $e \in
E(G)$ by $color(e)$. For a vertex $v$ of $G$, the {\it}{color
neighborhood $CN(v)$} of $v$ is defined as the set $\{color(e) | e$
is incident on $v\}$ and the {\it}{color degree} of $v$, denoted by
$d^c(v)$ is defined to be  $d^c(v) = |CN(v)|$.


A path in an edge colored graph with no two edges sharing the same
color is called a {\it rainbow path}. Similarly, a cycle in an edge
colored graph is called a {\it rainbow cycle} if no two edges of the
cycle share the same color. A survey on rainbow paths, cycles and
other rainbow sub-graphs can be found in \cite{kano}. Several
theorems and conjectures on rainbow cycles can be found in a paper
by Akbari, Etesami, Mahini and Mahmoody in \cite{AEMM}. 

Let $t$ denote the length of the maximum length rainbow path in $G$. In \cite{CL},
Chen and Li  studied the maximum length rainbow path problem in edge-colored graphs
and proved that if $G$ is an edge colored graph with $d^c(v) \geq k$ ($k \geq 8$), for every vertex $v$ of $G$, then $G$ has
a rainbow path of length at least $ \left \lceil \frac{3 k}{5}\right \rceil + 1$.
Chen and Li state in their paper that it was conjectured by Akira Saito, that $t \ge \left \lceil \frac {2k} {3} \right \rceil$.
They also state in their paper that they believe $t \ge k - c$ for some constant $c$, after showing
an example where the rainbow path cannot be more than $k-1$. 


In this note, we give a  short proof  to show that $t \ge \left \lceil \frac{3 k}{5}\right \rceil$, using
an entirely different method. Our proof is only
about 2 pages long. The draw-back is that our bound is less by 1, than the bound given by Chen and Li. 
We hope that the new approach adopted in this paper would eventually lead to the settlement of the conjectures by
Saito and/or Chen and Li. 





\subsection{Preliminaries}


All graphs considered in this paper are finite, simple and
undirected. A graph is a tuple $(V, E)$, where $V$ is a finite set
of vertices and $E$ is the set of edges. For a graph $G$, we use
$V(G)$ and $E(G)$ to denote its vertex set and edge set,
respectively. The neighborhood $N(v)$ of a vertex $v$ is the set of
vertices adjacent to $v$ but not including $v$. The degree of a
vertex $v$ is $d_v = |N(v)|$. A path is a non-empty graph $P=(V,E)$
of the form $V = \{p_1, p_2, \ldots , p_k\}$ and $E = \{ (p_1,
p_2), (p_2, p_3), \ldots , (p_{k-1}, p_k)  \}$, which we usually
denote by the sequence $\{p_1, p_2, \ldots, p_k\}$. The {\it length}
of a path is its number of edges. If $P = \{p_1, p_2, \ldots ,
p_k\}$ is a path, then the graph $C $ with $V(C) = V(P)$ and
$E(C)= P \cup \{(p_k, p_1)\}$ is a
cycle, and $|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,
\ldots, p_k, p_1\}$.




\section{Proof of the main results}


Let $G$ be an edge colored graph with $d^c(v) \geq k$, for every vertex $v$ of $G$ and $t$ be the maximum length
rainbow path in $G$. Let  $C$ denote  the set of
colors used in the edge coloring of $G$. The
following lemma ensures a rainbow path of length
$\left\lceil\frac{k+1}{2}\right\rceil$ starting from any vertex
in an edge colored graph.



\begin{lemma}\label{lemma1}
Let $G$ be an edge colored graph and $d^c(v) \geq k$, for every $v
\in V(G)$. Then, given any vertex $x$ in $G$ there exists a rainbow
path of length at least $\left \lceil\frac{k+1}{2} \right \rceil$
starting from $x$.
\end{lemma}




\begin{proof}
Let $P$ be a rainbow path in $G$ of maximum length, say $t$. Thus
$P$ contains $t+1$ vertices, $t$ edges and hence $t$ distinct
colors. Let $P = \{x = u_0, u_1, \ldots,
u_t=y\}$, $U = \{color(u_i,u_{i+1}), 0 \leq i \leq t-1)$ and $U^c =
C \setminus U$.
Select a subset $E(x)$ of edges incident on $x$ as follows: Let
$(x,u_1) \in E(x)$. Now, select $k-1$ more edges incident 
on $x$ and add to $E(x)$ so that all the $k$ edges in $E(x)$ have
different colors. Clearly it is possible to do this, since $d^c(x) \ge k$.  

 Let  $N_P(x) = \{ u_i \ : \ 1 \leq i \leq t \
\mbox{ and } (x,u_i) \in E(x)\}$, $N_{P^c}(x) = \{ a \in V(G)
\setminus V(P) \ : \ (x, a) \in E(x)\}$.


\vspace{.2cm}


\noindent {\bf Claim.} If $z \in N_{P^c}(x)$, then $color(x,z) \in
U- \{ color(x,u_1) \} $.


Suppose that $color(x,z) \in U^c$. As $z \notin V(P)$, $P' = \{z,
x=u_0, u_1, \ldots, u_t=y\}$ is a path. Moreover, $P'$ is a rainbow
path as $color(x, z) \in U^c$. Now $P'$ is a rainbow path in $G$ of
length $t+1$. This is a contradiction to the fact that $t$ is the length of the
maximum length rainbow path in $G$.
Also it is obvious that $color(x,z) \ne color(x,u_1)$. Hence the claim is true.


From the above claim  we infer that
$N_{P^C} (x)| \leq |U| - 1 = t - 1$. So, $|N_P(x)| \geq
k - (t - 1)$. But, number of vertices in $P$
excluding $x$ is $t$. So, $k - (t - 1) \leq t$. Hence, $t \geq
\frac{k+1}{2}$. Since $t$ is an integer, we have $t \geq \left
\lceil \frac{k+1}{2} \right \rceil$.
\end{proof}



The following lemma ensures that if the maximum length of a rainbow
path is small enough, then we can convert the maximum rainbow path
into a rainbow cycle by some simple modifications.


\begin{lemma}\label{lemma2}
Let $G$ be an edge colored graph and $d^c(v) \geq k$, for every $v
\in V(G)$. Let $t$ be the  length of the maximum length rainbow path in $G$. If $t
< \left\lceil \frac{3}{5}k \right \rceil $, then $G$ contains a
rainbow cycle of length $(t+1)$.
\end{lemma}



\begin{proof}
Assume for contradiction that there is no rainbow cycle of length
$t+1$ in $G$. Let $P = \{u_0(=x), u_1, u_2, \ldots, u_{t}(=y)\}$  be
a rainbow path of length $t$ in $G$. Let $U = \{color(u_i,
u_{i+1})$, $0 \leq i \leq t-1\}$ and $U^c = C \setminus U$, where
$C$ is the set of colors used to color the edges of $G$. Clearly
$|U| = t$. Let $T_x = \{ u_i  \ : 0 \leq i \leq t, \ (x, u_i) \in
E(G)$ and $color(x, u_i) \in U^c\}$ and let $T_y = \{ u_i \ : \ 0
\leq i \leq t , \ (y, u_i) \in E(G)$ and $color(y, u_i) \in U^c\}$.




First note that, $|\{ (x,z) \in E(G): color(x,z) \in U^c \}| \ge k -
t$. Moreover, if $(x,z) \in E(G)$ with $color(x,z) \in U^c$, then $z
\in V(P)$, i.e., $z = u_i$ for some $1 \le i \le t$, since otherwise
we would have a rainbow path of length $t+1$ in $G$. It follows that
$|T_x| \geq k - t$. By a similar argument, we get $|T_y| \ge k - t$.
Note that $u_0, u_1 \notin T_x$ since $u_0=x$ and color($x,u_1) \in
U$. Also, $u_t \notin T_x$, since if $(x,u_t)$ is an edge and is
colored using a color from $U^c$, then we already have a $t+1$
length rainbow cycle, contrary to the assumption. So, we can write
$T_x = \{ u_i \ : 2 \le i \le t-1  \mbox { and } color(x,u_i) \in
U^c \}$. By similar reasoning, we can write, $T_y = \{ u_i \ : 1 \le
i \le t-2  \mbox { and } color(y,u_i) \in U^c \}$. Define $M_x =
\{u_j \ : \ u_{j+1} \in T_x\}$.

\vspace{.2cm}

\noindent  {\bf Observation 1.}
 $|M_x| = |T_x|  \geq k - t$.

\vspace{.2cm}

\noindent {\bf Claim 1.} $M_x \cap T_y \neq \emptyset$.

If possible suppose $M_x \cap T_y = \emptyset$. Now, $|M_x| + |T_y|
\leq t - 1$, as both $M_x \subset V(P)$ and $T_y \subset V(P)$  and
number of vertices on $P$ excluding $x$ and $y$ is $t-1$. (Note that,
$x,y \notin M_x$ and $x,y \notin T_y$.) As $|M_x| \geq k - t$
and $|T_y| \geq k - t$ and $M_x \cap T_y = \emptyset$ by
assumption, we have $k - t + k - t \leq t-1$. That is, $2 k \leq 3t - 1$. So, $t \geq \frac{2 k+1}{3}$. This is a
contradiction to the fact that $t < \left\lceil \frac{3}{5}k
\right\rceil $. Hence Claim 1 is true.

\vspace{.2cm}


\noindent {\bf Claim 2.} If $u_i \in M_x \cap T_y$, then $color(y,
u_i) = color(x, u_{i+1})$.


Suppose Claim 2 is false. That is, $ \exists u_i \in M_x \cap
T_y$ such that  $color(y, u_i) \neq color(x, u_{i+1})$. Now consider the
cycle: $CL = \{x, u_1, \ldots, u_i, y, u_t, u_{t-1},$ $\ldots,
u_{i+1}, x\}$. Clearly $CL$ is a rainbow cycle, as $color(y, u_i)
\neq color(x, u_{i+1})$,  $color(y, u_i) \in U^c$ and $color(x,
u_{i+1}) \in U^c$. Note that the length of $CL$ is $t+1$, as we
removed exactly one edge, namely $(u_i, u_{i+1})$ from $P$ and added
two new edges, namely $(y, u_i)$ and  $(x, u_{i+1})$ to $CL$. So, the
length of $CL$ is $t-1+2=t+1$, contradiction to the assumption.
Hence, we can infer that if $u_i \in M_x \cap T_y$, then $color(y,
u_i) = color(x, u_{i+1})$.




Let $S_y = \{  v \in V(P) - (M_x \cup \{ y, u_{t-1} \} )     \ : \
color(y, v) \in U  \}  \} $.


\vspace{.2cm}


\noindent {\bf Observation 2.}  $|M_x| + |T_y| + |S_y| - |M_x
\cap T_y| \leq t-1$.

Proof: This is because  $S_y$ is disjoint from $M_x \cup T_y$ and
$S_y \cup M_x \cup T_y \subseteq V(P) - \{ y, u_{t-1} \}$. (Note
that  $y (= u_t)$ and $u_{t-1}$ do not appear in $M_x$, $T_y$ or
$S_y$.)

\vspace{.1cm}

We partition the set $M_x \cap T_y$ as follows. Let $u_i \in M_x
\cap T_y$. If $color(u_i, u_{i+1})$ appears in one of the edges
incident on $y$, then $u_i \in A$ otherwise $u_i \in B$.

\vspace{.1cm}

\noindent {\bf Observation 3.}  $|T_y| \ge k - t + |B| $.

Proof: To see this first note that there are at least $k$ edges
of different colors
incident on $y$ (as by assumption, color degree of $y$ is at least
$k$)and at most $t- |B| $ of them can get the colors from $U$,
since $|B|$ colors in $U$ do not appear on the edges incident on
$y$, by the definition of $B$.
So, at least $k - t
+ |B| $ of the edges incident on $y$ have colors from $U^c$, and
clearly any $w$, such that $(y,w)$ is an edge, colored by a color in
$U^c$ has to be on $P$, since otherwise we have a longer rainbow
path. It follows that $|T_y| \ge k - t + |B|$.

\vspace{.1cm}

\noindent{\bf Claim 3.} If $u_i \in A$, then the edge incident on
$y$ with color $color(u_i, u_{i+1})$ has its other end point on the
rainbow path $P$. That is, if $w$ is such that $(y,w)$ is an edge
and $color(u_i,u_{i+1}) = color(y, w)$, then $w \in V(P)$.

Suppose Claim 3 is false. Let $(y, w) \in E(G)$ with
$color(y, w) = color(u_i, u_{i+1})$ and $w \notin V(P)$. Now,
consider the path: $P' = \{ w, y, u_{t-1}, u_{t-2}, \ldots, u_{i+1},
x (=u_0), u_1, \ldots, u_i\}$. Clearly $P'$ is a rainbow path as
$color(u_i,u_{i+1}) = color(y, w)$,  the edge $(u_i,u_{i+1}) \notin
E(P')$ and color$(u_{i+1},x) \in U^c$, since $u_i \in M_x$. Note
that, the length of $P'$ is $t+1$. This is a contradiction to the
fact that $t$ is the maximum length rainbow path in $G$. Hence Claim
3 is true.

\vspace{.1cm}

Now, partition $A$ as follows: if $u_i \in A$, then by the above
claim the edge incident on $y$ with the color $color(u_i, u_{i+1})$
has its other end point say $w$,  on $P$. If $w \in M_x$, then let $u_i
\in A_1$, else $u_i \in A_2$.

\vspace{.1cm}

\noindent {\bf Observation 4.}  $|M_x \cap T_y| = |A| + |B| = |A_1|
+ |A_2| + |B|$.

\vspace{.1cm}

\noindent {\bf Observation 5.}  $|S_y| \ge |A_2|$. To see this,
recall that $S_y = \{v \in V(P) -  (M_x \cup \{ y, u_{t-1} \})   \ : \ color(y, v) \in U 
 \} $. By definition of $A_2$, for each $u_i \in
A_2$ there exists a unique  vertex $w = w(u_i) \in V(P) - M_x$ such
that $(y, w)$ is an edge and $color(y,w) = color(u_i,u_{i+1}) \in
U$. Since $u_i \in A_2 \subset M_x$, we have $i <  t-1$ and thus
color$(u_i,u_{i+1}) \ne color(y,u_{t-1})$. Therefore $w(u_i)$ cannot be $y$ or $u_{t-1}$, for any $u_i \in A_2$.
 It follows that $\{w(u_i)
: u_i \in A_2 \} \subseteq  S_y$, and therefore we have $|S_y| \ge
|A_2|$.

\vspace{.2cm}

\noindent {\bf Claim 4.}   $|A_1| \leq \frac{|M_x|}{2}$.

Recall that, for each $u_i \in A_1$, there is a unique vertex
$w=w(u_i)$ such that $(y,w)$ is an edge with  $color(u_i, u_{i+1})=
color(y,w)$. Moreover, $w \in M_x$, by the definition of $A_1$ and
$A_1 \cup \{ w(u_i) : u_i \in A_1 \} \subseteq M_x$. Note that
$w(u_i)$ is uniquely defined for $u_i$ since it is the end point of
the edge incident on $y$ colored with the color of the edge
$(u_i,u_{i+1})$. Moreover,  $A_1 \cap \{ w(u_i) : u_i \in A_1 \} =
\emptyset$, since $A_1$ contains vertices which are end points of
edges from $y$, colored by the colors in $U^c$ whereas each $w(u_i)$
is the end point of some edge from $y$ which is colored by a color
in $U$. It follows that $2|A_1| \leq |M_x|$. That is, $|A_1| \leq
\frac{|M_x|}{2}$, as required.


Now, substituting $k - t + |B| $ for $|T_y|$ (by Observation 3),
$|A_2|$ for $|S_y|$ (by Observation 5), and $|A_1| + |A_2| + |B|=
|M_x \cap T_y|$ (by Observation 4) in  the  inequality of
Observation 2,  and simplifying we get $|M_x| + k - t  - |A_1|
\leq t - 1 $. Now using $|A_1| \le |M_x|/2$ (Claim 4) and
and simplifying we get $\frac{|M_x|}{2} + k - t  \leq t - 1$. Recall
that $|M_x| \geq k -t$ (Observation 1). Substituting and simplifying
we get, $t \geq \frac{3k + 2}{5}$. It follows that $t  \ge \left\lceil \frac{3}{5} k
\right \rceil $, contradicting the initial assumption. Hence the
Lemma is true.
\end{proof}







\begin{theor}
Let $G$ be an edge colored graph and $d^c(v) \geq k$, for every $v
\in V(G)$. If $t$ is the maximum length of a rainbow path in $G$,
then $t \geq \left \lceil\frac{3k}{5} \right\rceil$.
\end{theor}



\begin{proof}
If possible suppose $t < \left \lceil \frac{3
k}{5}\right\rceil $. By Lemma \ref{lemma2}, $G$ contains a
rainbow cycle of length $t+1$. Let $CL$ be this cycle. Note that,
$CL$ contains $(t+1)$ vertices and $(t+1)$ edges. Now, $t+1 \leq
\lceil \frac{3 k}{5} \rceil  $. Let $CL = \{u_0, u_1, \ldots,
u_t,  u_0\}$ and $V(CL^c) = V(G) \setminus V(CL)$. Let $U =
\{color(e) \ : \ e \in E(CL)\}$ and $U^c = C \setminus U$, where $C$
is the set of colors used to color the edges of $G$. Let
$F_i = \{ z \in V(CL^c) : (u_i,z) \in E(G)\}$.

\vspace{.1cm}

\noindent {\bf Claim 1.} $|F_i| \ge \left\lfloor\frac {2 k}
{5}\right\rfloor $. Moreover, for $z \in F_i$, $color(u_i, z) \in
U$.


First part follows from the fact that the color degree of $u_i$ is at least
$k$ as $d^c(u_i) \geq k$ and there are at most $\left \lceil\frac {3
k} {5} \right \rceil $ vertices in $CL$. If possible suppose
$color(u_i, z) \in U^c$. Now consider the path $P' = \{z, u_i,
u_{i+1}, u_{i+2}, \ldots,$ $u_{t},u_0,\ldots, u_{i-1} \}$. Clearly,
$P'$ is a rainbow path as $ color(u_i, z) \in U^c$ and $\{u_i,
u_{i+1}, u_{i+2}, \ldots, u_{t},$ $u_0, \ldots, u_{i-1} \}$ is
already a rainbow path being a part of the rainbow cycle $CL$. Note
that, the length of $P'$ is $t+1$. This is a contradiction to the
assumption that $t$ is the maximum length rainbow path in $G$. Hence
Claim 1 is true.

\vspace{.1cm}

Let $G' = (V', E')$, where $V'(G') = V(G)$ and $E'(G') = E(G)
\setminus \{e \in E(G) : \  color(e) \in U\}$. Clearly, in $G'$
there is no edge between $V(CL)$ to $V(CL^c)$, since by Claim 1,
every such edge is colored by a color in $U$.  Consider the induced
subgraph on $V(CL^c)$ in $G'$. Let $G'' = G'[V(CL^c)]$. Let $d^c(v)
\geq k'$ for every $v \in V(G'')$.

\vspace{.1cm}

\noindent {\bf Observation 1.} $k' \ge \left\lfloor \frac {2k}
{5}\right\rfloor $.

Proof: Clearly  $k' \geq k - |U| = k - (t+1) \ge k - \left\lceil
\frac{3 k}{5}\right\rceil  \geq \left\lfloor
\frac{2k}{5}\right\rfloor $.


\vspace{.2cm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\noindent Consider the following subset $U_0$ of $U$, defined by
$U_0 = U_1 \cup U_2$, where 
\begin{align*}
 U_1 &= \left\{ color(u_i,u_{i+1}) : 0 \le i
\le \left\lceil \frac {k} {5} \right\rceil \right\}, \\
U_2 &=  \left\{ color (u_i,
u_{i+1}) : (t+1) - \left \lceil \frac {k} {5} \right \rceil \le i
\leq t-1 \right\} \cup \{color(u_t, u_0)\}.
\end{align*}




\noindent {\bf Claim  2.}  $ \{ color(u_0,z) : z \in F_0\}
 \cap U_0 = \emptyset$.

Suppose not. Let $z \in F_0$ be such that $color(u_0,z)  \in U_0$.
Without loss of generality assume that $color(u_0,z) \in U_1 $. Then
consider the path $P^*$ = $(u_{\left \lfloor \frac {k} {5} \right
\rfloor}, \ldots, u_{t}, u_0,z)$, which is clearly a rainbow path,
since the edge of $CL$ with its color equal to $color(u_0,z)$ is not
there in this path. Also the length of $P^*$ is $t+1 - \left \lfloor
\frac {k} {5} \right \rfloor$. By Observation 1, $G''$ has minimum color
degree at least $\left\lfloor \frac {2 k} {5}\right\rfloor $, and
therefore by Lemma \ref {lemma1}, $G''$ has a rainbow path of length
at least $\left\lceil\frac {k} {5}\right\rceil$ starting from the vertex  $z$, let us call this
path $P''$. Clearly concatenating the path $P''$ with $P^*$ we get a
rainbow path since colors used in $P^*$ belong to $U$ whereas the
colors used in $P''$ belong to $U^c$. Moreover, the length of this
rainbow path is at least $t+1$, a contradiction, to the assumption
that $t$ is the length of the maximum rainbow path in $G$.


Now we complete the proof as follows: In view of Claim 2, and Claim
1, we know that $|F_0| \leq |U - U_0|$. But $|U - U_0| \le
\left\lceil\frac{3 k} {5}\right\rceil  - (\left\lceil\frac {2 k }
{5}\right\rceil + 1 ) \leq \left\lceil\frac{k}{5}\right\rceil <
\left\lceil\frac {2 k} {5}\right\rceil$ (since we can assume $k \ge
5$: for smaller values of $k$, the Theorem is trivially true). This
is a contradiction to the first part of Claim 1.
\end{proof}






\begin{thebibliography}{5}


\bibitem{AEMM} S.~Akbari, O.~Etesami, H.~Mahini, M.~Mahmoody. \newblock On rainbow
cycles in edge colored complete graphs. \newblock {\em Australasian Journal of
Combinatorics} 37, 33-42, 2007.

\bibitem{CL} H. Chen and X. Li. \newblock Long heterochromatic paths in edge-colored graphs. \newblock
{\em The Electronic Journal of Combinatorics}. {\bf 12} (2005), \#R33.


\bibitem{GMo} H. Gebauer, F. Mousset. \newblock On rainbow cycles and paths. \newblock (2012). \arxiv{1207.0840} 


\bibitem{GM} A. Gy{\' a}r{\' a}s, M. Mhalla. \newblock Rainbow and
orthogonal paths in factorizations of $K_n$. \newblock {\em Journal of
Cominatorial Designs}, 18(3):167-176, 2010.


\bibitem{kano} M. Kano, X. Li. \newblock Monochromatic and heterochromatic subgraphs
in edge-colored graphs - a survey. \newblock {\em Graphs Combin}. 24 (2008),
237 - 263.

\end{thebibliography}

\end{document}














