My sixteen graph theory students

Question

I will have sixteen students in my graph theory course this semester. In our first session I asked each of them with which of the other 15 students in the class they were already acquainted before the course. The graph below is the result, where for convenience students have been labelled 0 through 15.

For a certain activity, I have been able to split the 16 students into three groups. In the first of the groups, everyone was already acquainted with everyone else in the group, while in the second group no one had met any of the other members of the group. The third group was made up of just five students who did not belong to either of the first two groups.

Who were the five students in this last group?

Answer 1

The problem in ZIMPL format:

set students := {0 .. 15};
set groups := { 1 .. 3};

set pairs := { <s, t> in students * students with s < t };

set relations := {<0,1>,<0,4>,<0,7>,<0,12>,<0,13>,<0,15>,<1,2>,<1,5>,<1,6>,<1,7>,<1,8>,<1,12>,<1,13>,<1,15>,<2,5>,<2,7>,<2,8>,<2,9>,<2,10>,<2,11>,<2,13>,<2,14>,<2,15>,<3,4>,<3,6>,<3,11>,<3,15>,<4,5>,<4,6>,<4,7>,<4,8>,<4,9>,<5,6>,<6,7>,<6,9>,<6,10>,<6,11>,<6,13>,<7,9>,<7,10>,<7,13>,<7,15>,<8,9>,<8,12>,<8,15>,<9,10>,<9,11>,<9,15>,<10,11>,<10,12>,<10,13>,<10,15>,<11,13>,<11,14>,<11,15>,<12,13>,<12,14>,<12,15>,<13,14>,<13,15>};

var in_group[students * groups] binary;

# maximize cost: 0;

subto one_group_each: forall <s> in students: (sum <g> in groups: in_group[s,g]) == 1;
subto group_1_all_related: forall <s,t> in pairs: if not (<s,t> in relations) then in_group[s,1] + in_group[t,1] <= 1 end;
subto group_2_all_related: forall <s,t> in pairs: if <s,t> in relations then in_group[s,2] + in_group[t,2] <= 1 end;
subto group_3_has_five: (sum <s> in students: in_group[s,3]) == 5;

Solution from SCIP:

objective value:                                    0
in_group#0#2                                        1   (obj:0)
in_group#1#1                                        1   (obj:0)
in_group#2#1                                        1   (obj:0)
in_group#3#2                                        1   (obj:0)
in_group#4#3                                        1   (obj:0)
in_group#5#2                                        1   (obj:0)
in_group#6#3                                        1   (obj:0)
in_group#7#1                                        1   (obj:0)
in_group#8#2                                        1   (obj:0)
in_group#9#3                                        1   (obj:0)
in_group#10#2                                       1   (obj:0)
in_group#11#3                                       1   (obj:0)
in_group#12#3                                       1   (obj:0)
in_group#13#1                                       1   (obj:0)
in_group#14#2                                       1   (obj:0)
in_group#15#1                                       1   (obj:0)

The solution in words:

Students 1, 2, 7, 13, and 15 are in the first group; students 0, 3, 5, 8, 10, and 14 are in the second group; and students 4, 6, 9, 11, and 12 are in the last group.