Thread: Graph Theory - Trees and Paths

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 which satisfy the following

i)
ii) 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.

Notice that you are required to find paths ending in leaves (except one which is used to cover a single leaf ) that pass through a single common vertex. So you only need to root the tree at a suitable vertex such that the largest of the subtrees (in terms of the number of leaves) of the root does not exceed the sum of the others by more than 1.