Template:Alternate solutions

Let us start with arbitrarily breaking up the group of students into 2 groups, one in each room. Let the size of the largest clique in one room (room A) be n and the size of the largest clique in the other room (room B) be m. We consider the case where m>n. Let us take one student from room B to room A. This can do one of three things, it can decrease the difference between the size of the largest clique in room B and the size of the largest clique in room A by a factor of 0,1 or 2. We repeatedly perform this operation until for some k the largest clique in room A has size k, and the largest clique in room B has size k+1.

We consider two cases. Case 1- Let the number of k+1 cliques in B be 1. This case has two subcases. If the number of k cliques in room B has size 1 then since the largest clique cannot be of size 2k+1, we can send one member of the k+1 clique in room B to room A without disturbing the size of the sole k clique in room A. This gives us the largest size of cliques in each room to be k. Second subcase- If the number of k cliques in in room A is more than one. Given any k clique in A there is a member of that clique such that it is not friends with all of the members of the k+1 clique in B, or else the largest clique overall would have size 2k+1. If such a member named "a" is contained in all of the k cliques in A then there is a member named "b" of the k+1 clique in B who is not friends with a, and we send b to room A which gives us the size of the largest clique in both rooms as k. If such a member "a" is not contained in all of the k cliques, then we send it to room B thereby decreasing the number of k cliques in room A by 1. This process continues until either we have 2 k+1-cliques in room A, which will be the next case, or we have 1 k-clique in room A and 1 k+1-clique in room B which is the previous case.

Case 2- The number of k+1 cliques in B is 2. Let the 2 cliques be C,D. If there is a student "a" in C\D or D\C such that sending a over to the other room increases the size of the largest clique in room A by 1, then we do so and finish our job. In the other case we assume this is not possible. Now there is an "a" in C\D and a "b" in D\C such that a and b are not friends, otherwise the cliques C, D would be the same. We send a,b to the other room. This finished our job since sending a,b to the other room does not increase the size of any k clique in room A by assumption and since a,b are not friends it does not increase the size of a k-1 clique by 2.

Case 3- The number of k+1 cliques in B is m>2. Let C be the intersection of all these k+1 cliques. Now consider a k+1 clique E. If there is an "a" in E\C such that sending "a" to room A increases the size of a k clique by 1 then we send "a" to room A to finish the job, since removing "a" does not affect the size of all of the k+1-cliques in B. If not then we consider 2 cases. SubCase 1- If removing "a" reduces the number of k+1 cliques in B to 1. There must be a "b" in a k+1 clique in B such that "b" is not friends with "a", otherwise"a" must lie in all the k+1 cliques. If sending "b" increases the size of a k-clique in A, then we send "b" to A without affecting the size of the k+1-cliques in B that contain "a" and finish the job. If sending "b" or "a" to A does not accomplish this, then sending both "a" and "b" to A will not increase the size of any k-clique in A and not increase the size of any k-1-clique to k+1 since "a" and "b" are not friends, and will reduce the size of all k+1-cliques in B by one, since "a" is in m-1 of these cliques, and "b" is in the remaining one. This will finish the job. SubCase 2- If removing "a" reduces the size of the set of k+1-cliques in B to more than 1 then we repeat case 3 until we are left with SubCase 1 or Case 2.