In a forest each of $n$ animals ($n\ge 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$.
### Part (a)

1. **Graph Representation and Hamiltonian Cycles**:
   - Consider the problem in terms of graph theory. Each cave is a vertex, and each path between caves is an edge. Since there is exactly one path between any two caves, the graph is a complete graph \( K_n \).
   - A campaign-making animal visits each cave exactly once and returns to its own cave, forming a Hamiltonian cycle in \( K_n \).

2. **2-Factorization of \( K_n \)**:
   - A 2-factor of a graph is a spanning 2-regular subgraph, which means each vertex has degree 2. In the context of \( K_n \), a 2-factor is a collection of disjoint cycles covering all vertices.
   - For \( K_n \) with \( n \) being an odd prime, it is known that \( K_n \) can be decomposed into \(\frac{n-1}{2}\) Hamiltonian cycles. This is because each 2-factor in \( K_n \) for odd \( n \) can be a single cycle (Hamiltonian).

3. **Proof of Maximum Number of Campaign-Making Animals**:
   - Each campaign-making animal corresponds to a Hamiltonian cycle in \( K_n \).
   - Since \( K_n \) can be decomposed into \(\frac{n-1}{2}\) Hamiltonian cycles, the maximum number of campaign-making animals is \(\frac{n-1}{2}\).

\[
\boxed{\frac{n-1}{2}}
\]

### Part (b)

1. **Specific Case for \( n = 9 \)**:
   - For \( n = 9 \), we need to find the maximum number of campaign-making animals.
   - Since 9 is an odd number, we can use the result from part (a).

2. **Calculation**:
   - Using the formula \(\frac{n-1}{2}\), we substitute \( n = 9 \):

\[
\frac{9-1}{2} = \frac{8}{2} = 4
\]

3. **Verification with Example Hamiltonian Cycles**:
   - The given example Hamiltonian cycles for \( n = 9 \) are:
     - 123456789
     - 137946258
     - 148275936
     - 153869247
   - These cycles confirm that there are indeed 4 Hamiltonian cycles, matching our calculation.

\[
\boxed{4}
\]