We've colored edges of $K_n$ with $n-1$ colors. We call a vertex rainbow if it's connected to all of the colors. At most how many rainbows can exist?

[i]Proposed by Morteza Saghafian[/i]
1. **Base Case:**
   - For \( n = 2 \), \( K_2 \) has 1 edge and 1 color. Both vertices are connected by this single edge, making both vertices rainbow. Thus, the number of rainbow vertices is 2, which matches the formula \( n \) for even \( n \).

2. **Inductive Step:**
   - Assume the statement is true for \( K_{2k} \) and \( K_{2k+1} \). We need to prove it for \( K_{2k+2} \) and \( K_{2k+3} \).

3. **Even \( n \):**
   - Consider \( n = 2k \). We need to show that \( K_{2k+2} \) can have \( 2k+2 \) rainbow vertices.
   - Construct \( K_{2k+2} \) by taking two copies of \( K_k \) where each vertex in \( K_k \) is a rainbow vertex. Connect these two \( K_k \) graphs with a complete bipartite graph \( K_{k,k} \) using the remaining \( k \) colors.
   - Each vertex in the bipartite graph will be connected to all \( k \) colors from the other \( K_k \) graph, ensuring that all vertices in \( K_{2k+2} \) are rainbow.

4. **Odd \( n \):**
   - For \( n = 2k+1 \), we need to show that \( K_{2k+3} \) can have \( 2k+2 \) rainbow vertices.
   - Start with \( K_{2k+2} \) where all vertices are rainbow. Add an additional vertex \( v \) and connect it to all other vertices using a new color \( c_{2k+2} \).
   - The new vertex \( v \) will not be a rainbow vertex because it is only connected to one color. However, all other \( 2k+2 \) vertices remain rainbow.

5. **Algorithm for Coloring:**
   - Label the vertices \( v_1, v_2, \dots, v_{4k+2} \) and the colors \( c_1, c_2, \dots, c_{4k+2} \).
   - Color the edge \( v_{2i+1}v_{2i+2} \) with color \( c_{2i} \).
   - For each \( j \) from 0 to \( k-1 \) and \( i \) from 0 to \( 2k+1 \), color the edges \( v_{2i+1-(2j+1)}v_{(2i+2)+(2j+2)} \) and \( v_{(2i+1)-(2j+2)}v_{(2i+2)+(2j+1)} \) with color \( c_{2i} \).
   - For odd-length edges, color every other edge traversed in a cycle with color \( c_t \) and the remaining edges with color \( c_{n-t} \).

6. **Conclusion:**
   - For even \( n \), \( K_n \) can have \( n \) rainbow vertices.
   - For odd \( n \), \( K_n \) can have \( n-1 \) rainbow vertices.

\(\blacksquare\)

The final answer is \( \boxed{ n } \) for even \( n \) and \( n-1 \) for odd \( n \).