It suffices to show that $k$ cannot be $3$. Indeed, assume we have this result; assume further that there is a coloring of a $K_n$ for some $k \ge 4$. Let the colors be $c_1, c_2, \ldots, c_k$. Then we can re-color all edges colored from $\{c_4, \ldots, c_k\}$ in $c_3$ while still satisfying $(i)$ and $(ii)$. This would then give a valid coloring of $K_n$ for $k = 3$, a contradiction. Let the three colors be red, green, and blue. $\bold{FACT}$: For four vertices $A, B, C, D$ such that $AB$ and $AD$ are red while $BC$ is green and $CD$ is blue, it follows from $(ii)$ that $AC$ must be red. An idea is to successively construct edges of the graph and then to use the fact above to show that there must then be infinitely many vertices, a contradiction. Begin with a red edge between some $A$ and $R_1$. From $(i)$, there exists $G_1$ such that $AG_1$ and $R_1 G_1$ are each green. Again by $(i)$, there exists $B_1$ such that $B_1 G_1$ and $B_1 R_1$ are each blue. From the fact above, $B_1 A$ is also blue. However, there must exist more vertices, since among these four there are none such that $G_1$ and $B_1$ can satisfy $(i)$ with color red. We then inductively construct $R_i, G_i, B_i$ in that order for $i = 1,2,\ldots$. We now verify that from each $R_i$ constructed, all edges to previously constructed vertices are red, and similarly for $G_i$ in green and $B_i$ in blue. Assume the existence of vertices $\{A, R_1, G_1, B_1, R_2, G_2, B_2, \ldots, R_{i-1}, G_{i-1}, B_{i-1}\}$ such that all edges from $R_m$ to previously constructed vertices are red for $m = 1,2,\ldots, i-1$ and similarly for $G_m$ and $B_m$. Then among the constructed vertices, there is no vertex to satisfy $(i)$ with $G_{i-1}$ and $B_{i-1}$ using red. Then there is another vertex $R_i$ such that $G_{i-1} R_i$ and $B_{i-1}R_i$ are each red. By the fact, all edges from $R_i$ to previous vertices are red. Proceed with a similar argument to show that there is another distinct vertex $G_i$ with edges in green to all other vertices already constructed. Argue similarly for $B_i$. This completes the inductive step and ensures the addition of three new vertices to the graph construction at each step, yielding infinitely many vertices.