I am having difficulties with this problem.

Let T be a tree with k leaves and set [tex]t=ceiling(k/2)/MATH]. Prove that there exists paths $\displaystyle P_1,P_2, \dots P_t$ which satisfy the following

i) $\displaystyle \cup_{i=1}^{t} P_i = T$

ii) $\displaystyle V(P_i) \cap V(P_j) \neq \phi$ for every i<j.

EDIT: going over my work i realized that my proof doesn't hold. So I'd appreciate any help on where to start. Induction seems to be the natural choice but i can't get it to work for any parameter.