Does anyone know Lovasz's solution??

Any solution?

For a clique with $m$ vertices, we define its value as $m-1$. Reformulation: If all vertices of a simple graph $G$ can be partitioned into $k$ sets so that for any two sets there are two vertices joined by an edge each in one of them, then they can also be partitioned into cliques and the total value (sum of values) of all cliques is at least $k-1$. Proof: Use induction on $k$. Pick a set $S$ arbitrarily. By induction hypothesis, the subgraph composed of $V(G)\backslash S$ can be partitioned into cliques $\{K_i\}_{i \ge 1}$ with their total value at least $k-2$. Firstly, consider each vertex in $S$ as a clique for use. We deal with two cases: Case 1: No $V(K_i)$ is completely covered by neighbors of $S$ in $V(G)\backslash S$ (denoted by $N(S)$). Then, each $K_i$'s value is at least $|V(K_i) \cap N(S)|$. Therefore, the total value of $\{K_i\}$ again is at least $|N(S)| \ge k-1$. Case 2: There is a $V(K_i)$ completely covered by $N(S)$. Then we can decompose this clique into small cliques and attach each small clique with its unique neighbor in $S$ respectively, forming new cliques. As a result, the total value of cliques in the whole graph $G$ increases by at least 1.

Cool problem! Let $G$ be the obvious graph corresponding to the students in the school. Let's label the classes $C_1, C_2, C_3, \cdots, C_k$ in an arbitrary manner. Claim. For each $2 \le i \le k$, there is a way to select empty (no friendships) vertex-induced subgraphs of $G$ satisfying the following properties. 1. Each of the subgraphs contains at least two vertices. 2. Each of the subgraphs contains no vertices not in $C_1 \cup C_2 \cup \cdots \cup C_i$ 3. If we consider the graph $G'$ on $i$ vertices where we connect $a$ and $b$ iff $C_a, C_b$ are in the same subgraph at least once, then $G'$ is connected. 4. The vertex sets of the subgraphs are disjoint. 5. The sums of the sizes of the subgraphs minus one is equal to $i-1$. Proof. The proof goes by induction on $i.$ When $i = 2$, this is obvious. Suppose it holds for $i = t.$ That is, there exist complete subgraphs $G_1, G_2, G_3, \cdots, G_x$ of $G$ which satisfy the four conditions above. Consider the graph $H$ with $x$ vertices labelled $1, 2, \cdots, x$ where $a, b$ are connected iff there is some $1 \le r \le i$ so that $G_a, G_b$ both contain a vertex of $C_r.$ This graph must be a tree (left as exercise to the reader). We consider a few cases. Case 1. There is some vertex $v \in C_{t+1}$ and $w \in C_j$ for some $1 \le j \le t$ so that $w$ is not in any of the $G_i$'s and $v, w$ are not acquainted. Then, simply add the empty subgraph induced by the vertices $v, w.$ Case 2. There is not such a vertex. Consider vertices from each of the sets $C_1, C_2, C_3, \cdots, C_t$ which don't know some vertex in $C_{t+1}.$ By assumption, these vertices must all lie in $G_i$'s. For a $1 \le j \le t$ which has vertices from multiple $G_i$'s, we will say that its leader is the $G_a$ for which the common vertex of $G_a, C_j$ isn't connected to some vertex in $C_{t+1}.$ The other $G_i$'s in $C_j$ will then be said to bow down to $G_a.$ Consider the "bow down" digraph. It is clearly acyclic, and so there must exist a $G_a$ which bows down to no other $G_j.$ Now, let $V$ be the set of vertices in $C_{t+1}$ which don't know somebody in $G_a.$ By assumption, the set of non-neighbors of $V$ covers $G_a$ completely. Since $G_a$ is empty, we can now easily partition $G_a \cup V$ into empty subgraphs, each of which has exactly one vertex of $V.$ Then, the new size minus one is $|G_a| - 1$ rather than $|G_a|$, so condition 5 is now satisfied. Clearly, conditions 1, 2, 4 are satisfied. It remains only to check that condition $3$ is satisfied. However this is obvious. We essentially just broke up $G_a$ and then glued them together with $V$. As we've considered all cases, the induction is complete. $\blacksquare$ Apply the claim when $i = k$. Now, consider splitting the vertices of the graph into the subgraphs given by the claim and singletons. This partition clearly works. $\square$

We consider a graph $G$ where two vertices are connected iff they are not friends. We are given that vertices of $G$ can be partitioned into $k$ groups $H_1,H_2,\ldots,H_k$ such that there is an edge between any two groups. Our problem is equivalent to showing that $G$ can be partitioned into some cliques $\{C_i\}_{i \ge 1}$ such that $$ \sum_{i \ge 1} (|C_i| - 1) \ge k-1 $$We solve the problem using induction on $k$. Base case $k=1,2$ are direct. We perform the inductive step now. WLOG assume that between any two groups precisely one edge is there and there are no edges between the same group (as we can delete other edges otherwise). Case 1: There is a group $H$ such that at it has $\ge 2$ non-isolated vertices. Let $v_1,v_2,\ldots,v_l$ ($l \ge 2$) be the non-isolated vertices of $H$. For each $1 \le i \le l$, let $S_i$ be the set of groups $H_j$ such that $v_i$ is connected to some vertex in $H_j$. Consider the graphs $$ G_i = v_i \cup S_i \qquad \forall ~ 1 \le i \le l$$These graphs form a partition of $G$. For each $i$, by induction hypothesis we can divide $G_i$ into some cliques $\{D_j\}_{j \ge 1}$ such that $$ \sum_{j \ge 1} (|D_i| - 1) \ge |S_i| $$Combing all such cliques $D_i$ in the main graph $G$ we get $$\sum_{i \ge 1} (|C_i| - 1| \ge \sum_{i=1}^l |S_i| = k -1$$So we are done. Case 2: Each group contains only $1$ non-isolated vertex. Then there is $k$-clique in $G$, which of course suffices.

Here is a smoothing approach. Let $\overline{G}$ be the complement of $G$ WLOG there exists exactly one edge from $V_i$ to $V_j$ in $\overline{G}$, for if there are more than one we can delete the additional edges. Let $a_{i,j}$ denote the vertex in $V_i$ adjacent to $a_{j,i}$. We have if $i,j,k$ are pairwise distinct and $a_{i,j}\ne a_{i,k}$, then $N(a_{i,j}) \cap N(a_{i,k})= \emptyset$ by the above assumption. Suppose $a_{i,j}\ne a_{i,k}$. Consider $\overline{G'}$ be the graph where $a_{i,k}$ has no neighbours, while $a_{i,j}$ has neighbours $N(a_{i,j}) \cap N(a_{i,k})= \emptyset$ (where $N$ is the neighbourhood in $\overline{G}$). Consider a coloring of $G'$, then let $C$ be the set of vertices that are colored the same color as $a_{i,j}$ and call the color 1. This means in $\overline{G'}$ they are a clique. Also, call the color of $a_{i,k}$ 2. We can color $G$ as follows: color the vertices in $(C\cap N(a_{i,j}))\cup a_{i,j}$ with color 1 and vertices in $(C\cap N(a_{i,k})) \cup a_{i,k}$ with color 2, and all other vertices in $G$ with the same color as that of $G'$, which must work. It follows $\chi(G)\le \chi(G')$. Repeatedly doing this step gives $\overline{G'}=K_k$, so $\chi(G)\ge \chi(G')=n-k+1$, as needed.

https://artofproblemsolving.com/community/c6h2849596p25358189