Prove there exist two sets with edges of unique colors in a colored complete graph Let $G$ be a complete graph with edges of blue or red. Between the edges of each $4$ vertices, there exists a triangle with just blue/red edges.
Prove there is a decomposition of vertices into two parts ($S$ and $T$) so that edges in part $T$ are blue and edges in part $S$ are red. Please note that $S$ or $T$ could be empty and without any vertices.
The above problem can be converted to the following problem easily:
Let $G$ be a graph. Suppose $X$ is a set of $4$ vertices in $G$. There exist a cycle of size $3$ either in $X$ or Complement of $X$. Prove vertices of $G$ can decompose to a clique and an independent set.
Thanks in advance for your help!
 A: By a "red clique" I mean a set of vertices such that all edges between them are red. Let $S$ be a red clique of maximum possible size, and let $T$ be the complement of $S$. I claim that all edges joining two vertices in $T$ are blue.
Assume for a contradiction that there are two vertices $v,w\in T$ such that the edge $vw$ is red. Each of those vertices is joined by a blue edge to at least one vertex in $S$, otherwise we could add it to $S$ and get a bigger red clique.
First, suppose we can find two distinct vertices $x,y\in S$ such that $vx$ and $wy$ are blue. Then $xy$ is red, and the set $v,w,x,y$ contains no triangle with all of its edges the same color.
It we can't find two distinct vertices $x,y\in S$ as in the preceding case, then there is only one vertex in $S$, call it $x$, which is joined to $v$ by a blue edge, and the same $x$ is the only vertex in $S$ joined to $w$ by a blue edge. But then $(S\setminus\{x\})\cup\{v,w\}$ is a red clique containing one more vertex that $S$, a contradiction.
Remark. This exercise says that a graph, which does not contain $P_4$ or $C_4$ or $\overline{C_4}$ (the complement of $C_4$) as an induced subgraph, is a split graph. This sufficient condition for a split graph is certainly not necessary, seeing as $P_4$ is a split graph. In fact, a graph is a split graph if and only if it does not contain $C_5$ or $C_4$ or $\overline{C_4}$ as an induced subgraph, but proving that would be a more difficult exercise.
