In the language of graph theory: Let $G=(V,E)$ be a graph with $|V|=9$ that does not contain $K_4$ as a subgraph. Prove that $G$ is $4$-colorable. [Corrected.]

... which is false if you drop the $|V|=9$ condition as manuel has.

Any solution? I tried this for three hours but in vain. Superhard!

Here is my simple, low-tech solution to this difficult problem. More elegant or technical solutions are welcome. We consider a graph with vertices representing the people. The edge $\overline{v_iv_j}$ is blue when people $i$ and $j$ know each other, and red otherwise. The problem is equivalent to showing that the edge-induced subgraph of blue edges in $K_9$ is $4$-colorable. We start with a lemma. Lemma. The edges of $K_6$ are colored red or blue in such a way that there is no blue $K_4$ and if $B_6$ is the edge-induced subgraph of blue edges, then $\chi \left (B_6 \right) > 3$. Then all the red edges of $K_6$ form a cycle of length $5$. Proof. We first claim that under conditions of the lemma, there is no red $K_3$. It is well known that $R(3,3) = 6$ (see here for a proof), so there is a monochromatic $K_3$. Label the vertices of $K_6$ $v_1, v_2, \dots , v_6$. Suppose, for contradiction, that there is a red $K_3$, which, WLOG, we suppose is $v_1v_2v_3$. If some edge $\overline{v_iv_j}$, where $i,j \in \{4,5,6\}$, is red, then the $3$-partition $\{v_1,v_2,v_3 \}, \{v_i, v_j \}, \{v_k \}$, where $k \not \in \{1,2,3,i,j\}$, shows that $\chi (B_6) = 3$, which is forbidden. Hence $v_4v_5v_6$ is a blue $K_3$. $(\bigstar)$. Hence $\forall i \in \{1,2,3 \}, \exists j \in \{4,5,6\} \text{ such that } \overline{v_iv_j} \text{ is red}$, otherwise we would have a blue $K_4$. Suppose, WLOG, that $\overline{v_1v_4}, \overline{v_2v_4}$ are red. Then $v_1v_2v_4$ is a red $K_3$, so that $v_3v_5v_6$ is a blue $K_3$ from $(\bigstar)$. If now $\overline{v_3v_4}$ is blue, then $v_3v_4v_5v_6$ is a blue $K_4$. Otherwise, $\overline{v_3v_4}$ is red, and we have the $3$-partition $\{v_1,v_2,v_3,v_4\}, \{v_5\}, \{v_6\}$, so that $\chi (B_6) = 3$, and we have our contradiction. Therefore there is no red $K_3$, and our claim is true. We now show that all the red edges of $K_6$ form a cycle of length $5$. WLOG, let $\overline{v_1v_2}, \overline{v_3v_4}$ be red. If all edges $\overline{v_iv_j}$, where $i \in \{1,2\}, j \in \{3,4\}$ are red, then we have a $3$-partition $\{v_1, v_2, v_3,v_4\}, \{v_5\}, \{v_6\}$, which is forbidden. Hence, WLOG, let $\overline{v_2v_4}$ be blue. One of the edges in the vertex-induced subgraph $v_2v_4v_5v_6$ must be red: WLOG, let this be $\overline{v_4v_6}$. Then $\overline{v_3v_6}$ is blue (otherwise $v_3v_4v_6$ is a red $K_3$) and $\overline{v_3v_5}$ is blue (otherwise we have a $3$-partition $\{v_1, v_2\}, \{v_3, v_5 \}, \{v_4, v_6\}$). If $\overline{v_1v_3}$ is red, then $\overline{v_2v_5}$ must be blue and $\overline{v_2v_6}$ is red. Then $\overline{v_1v_6}, \overline{v_1v_5}, \overline{v_4v_5}, \overline{v_1v_4}$ are all blue, so our red edges are $\overline{v_1v_2}, \overline{v_2v_6}, \overline{v_6v_4}, \overline{v_4v_3}, \overline{v_3v_1}$, which form a cycle of length $5$. If $\overline{v_1v_3}$ is blue, then similar arguments produce a contradiction. Thus our proof of the lemma is complete. $\Box$ Consider now the complete graph $K_9$, with vertices $v_1, v_2, \dots , v_9$. It is well known that $R(3,4) = 9$ (see here for a proof), and since there is no blue $K_4$, there must be a red $K_3$. WLOG, we let $v_7v_8v_9$ be the red $K_3$. If the edge-induced subgraph of blue edges in the vertex-induced subgraph $v_1v_2 \dots v_6$ is $3$-colorable, then we are done. Otherwise, from the lemma, we can assume, WLOG, that $\overline{v_1v_2}, \overline{v_2v_3}, \overline{v_3v_4}, \overline{v_4v_5}, \overline{v_5v_1}$ are red. For $k \in \{7,8,9 \}$, we have four cases depending on how many of the $\overline{v_kv_6}$ are blue. Case 1. None of the $\overline{v_kv_6}$ are blue. Then we have the $4$-partition $\{v_6, v_7, v_8, v_9\}, \{v_1, v_2\}, \{v_3, v_4\}, \{v_5\}$. Case 2. Exactly one of the $\overline{v_kv_6}$ is blue (WLOG $\overline{v_7v_6}$). Then at least three of the edges $\overline{v_7v_i}$, for $i \in [1,5]$ are red, otherwise we have a blue $K_4$. WLOG, suppose $\overline{v_7v_i}$ is red when $i \in \{1,2,3\}$, so that we have a $4$-partition $\{ v_6, v_8, v_9\}, \{v_1, v_2, v_7\}, \{v_3, v_4\}, \{v_5\}$. Case 3. Exactly two of the $\overline{v_kv_6}$ are blue (WLOG $\overline{v_7v_6}, \overline{v_8v_6}$). Then as before, for $i \in [1,5]$ at least three of the $\overline{v_7v_i}$ and three of the $\overline{v_8v_i}$ are red. We can easily find the desired $4$-partition. Case 4. All the $\overline{v_kv_6}$ are blue. By similar arguments to before, we can find a $4$-partition. Hence the edge-induced subgraph of blue edges in $K_9$ is $4$-colorable, as required.