BALTIC-WAY 1997 Problem 19

In a forest each of $n$ animals $(n \geqslant 3)$ lives in its own cave, and there is exactly one separate path between any two of these caves. Before the election for King of the Forest some of the animals make an election campaign. Each campaign-making animal visits each of the other caves exactly once, uses only the paths for moving from cave to cave, never turns from one path to another between the caves and returns to its own cave in the end of its campaign. It is also known that no path between two caves is used by more than one campaign-making animal.

a) Prove that for any prime $n$, the maximum possible number of campaign-making animals is $\frac{n-1}{2}$;

b) Find the maximum number of campaign-making animals for $n=9$.