Also appeared in Bulgaria Winter Competition 2020, great problem! Take a vertex $x$ and a colour $c$ such that the number of neighbours of $x$ in colour $c$ is maximal (over all possible choices of $x$ and $c$). The edges incident at $x$ appear each in one out of $k$ colours, each colour occuring at most $N$ times, hence $Nk \geq n-1$. Now it suffices to argue $N \leq k-2$, as then $n \leq Nk + 1 = (k-1)^2$. For this, let $x_1,\ldots, x_N$ be the neighbours of $x$ in colour $c$. Since a triangle cannot have exactly two colours by the problem condition, each edge between $x_0,x_1,\ldots, x_N$ is coloured in $c$. The problem condition requires at least two colours to be present overall, so there must be a vertex $y$ adjacent to one of $x_0,\ldots,x_N$ in some colour $d\neq c$. Since a triangle cannot have exactly two colours by the problem condition, all edges from $y$ to $x_0, \ldots, x_N$ must be in pairwise different colours, and different from $c$. Thus $k \geq N+2$, as desired. Remark. Equality holds e.g. if $n = p^2$ for prime $p$, when one indexes the vertices by $(i, j)$ for $0 \leq i, j \leq p-1$ and colours the edge between $(i_1, j_1)$ and $(i_2, j_2)$ in $c \in [0, p - 1]$ such that $i_1 - i_2 \equiv c(j_1 - j_2) \pmod p$ and in colour $p$ if $j_1 = j_2$. I do not know whether there are constructions for a general perfect square.

ELMO SL 2024 C3 Let $n$ and $k$ be positive integers and $G$ be a complete graph on $n$ vertices. Each edge of $G$ is colored one of $k$ colors such that every triangle consists of either three edges of the same color or three edges of three different colors. Furthermore, there exist two different-colored edges. Prove that $n\le(k-1)^2$. Solution: simplest case- 1 = {12, 34, 56, .. disjoint edges} 2 = {disjoint edges} ... ==> k>=n, done. other case- {12, 13, 15, 18} \subset C1 ==> {23, 25, 28, 35, 38, 58} \subset C1. ==> E [ clique [1, 2, 3, 5, 8] ] \subseteq C1. We now delete this clique from the graph. Keep deleting cliques, until you reach a graph where all edges of a color are disjoint. [NOTE: two deleted cliques have at most one vertex common] the problem boils down to finding the minimum of: [k_i represents cliques] {[n\choose2 - ( k_1\choose2 + k_2\choose2 + ... + k_t\choose2)]/n} + t, for some t>1 where k_1+k_2+...+k_t <= 2n + t\choose2. This gives us a bound.

This felt a bit too easy. Say the colors are $C_1,C_2,...,C_k$ . For any vertex $v$ define its "diversity" $D_v$ as the number of distinct colors amongst the edges formed by joining $v$ to other vertices. Now say the vertexes are $V_1,V_2,...,V_n$ Pick any vertex $V_i$ which has the maximum diversity. there must exist a color $C_j$ which has a frequency of at max than $\frac{n-1}{D_{V_i}}$ amongst the edges $V_iV_1,V_iV_2,...,V_iV_n$ . and it appears atleast once. Pick any one $V_K$ such that $V_{i}V_K$ is of color $C_j$. Claim: The number of edges with color $C_j$ amongst the neighours of $V_i$ and $V_K$ is same. Proof: Observe that $V_iV_t$ is of color $C_j$ iff same holds for $V_KV_t$ this establishesh bijection . Claim: For any color $C_i$ other than $C_j$ its frequency amonst the edges from $V_K$ is at most $k-2$. Proof: Assume the contrary , Pick any $V_{i_1},V_{i_2},....,V_{i_{k-1}}$ such that $V_kV_{i_s}$ always has the color $C_j$ There are only $k-2$ possibilites for the color of $V_iV_{i_{s}}$ as it cant be $C_i$ or $C_j$ by PHP two will be equal Say its $V_{i_{s_1}}$ and $V_{i_{s_2}}$ by observing $V_kV_{i_{s_1}}V_{i_{s_2}}$ we know $V_{i_{s_1}}V_{i_{s_2}}$ is also of color $C_i$ , Now look at $V_iV_{i_{s_1}}V_{i_{s_2}}$ and we get contradiction!. Now observe then if we measure wrt $V_K$ the total no of vertices as the sum of the number of which of each color we have $n-1 \leq (k-2)(D_{K}-1)+\frac{n-1}{D_v} \leq (k-2)(D_v-1)+\frac{n-1}{D_v}$ $\implies (n-1)\frac{(D_v-1)}{D_v} \leq (k-2)(D_v-1)$ $D_v>1$ coz otherwise it would imply all edges have same color . So $n-1 \leq (k-2)D_v \leq (k-2)(k)$ So $n \leq (k-1)^2$

This problem appeared also 15 years ago on MEMO with a stronger thesis, but it is in fact known for even much longer. https://artofproblemsolving.com/community/c6h303623p1642764

Nice Problem! Let $v$ be a vertex in the graph. Let $v_i$ for $1 \le i \le n-1$ denote the rest of the vertices. Let $n_i$ for $1 \le i \le k$ denote the number of edges adjacent to $v$ of the color $C_i$. Claim 1: All the edges which have $v$ as an endpoint cannot be of the same color Proof: Suppose that all edges $vv_i$ have the same color $C$. Then if we notice the triangle $vv_iv_j$, then we can conclude that $v_iv_j$ also has the color $C$. This means that all the edges of the graph have the same color. Contradiction. Claim 2: $\max(n_i) \ge \frac{n-1}{k}$ Proof: Obvious by Pigeonhole Principle Claim 3: $k-2 \ge \max(n_i)$ Proof: WLOG assume that the edges of $v$ with $v_1, v_2, \cdots v_{\max{n_i}}$ are of the same color $C$. Take a vertex $v_j$ such that $vv_j$ is of a different color $D$(possible by claim 1). Then notice that none of the edges $v_jv_i$ have the same color. This is because suppose $v_jv_{{i_1}}$ and $v_jv_{{i_2}}$ have the same color $E$, then observing triangle $v_jv_{i_1}v_{i_2}$, we can conclude that $v_{i_1}v_{i_2}$ is also colored $E$. Also, $E$ is different from $C$ and $D$, because $vv_i$ is $C$ and $vv_j$ is $D$. Thus, the triangle $vv_{i_1}v_{i_2}$ has 2 distinct colors, which is impossible. Thus, there are $\max(n_i)$ colors in the edges of $v_jv_i$ and none of them are of color $C$ and $D$. Thus, $k-2 \ge \max(n_i)$ From Claim 2 and 3, we get, $k-2 \ge \frac{n-1}{k}$, which gives, $n \le (k-1)^2$