In a group of 2n students, each student has exactly 3 friends within the group. The friendships are mutual and for each two students A and B which are not friends, there is a sequence C1,C2,...,Cr of students such that A is a friend of C1, C1 is a friend of C2, et cetera, and Cr is a friend of B.
Every student was asked to assess each of his three friendships with: "acquaintance", "friend" and "BFF". It turned out that each student either gave the same assessment to all of his friends or gave every assessment exactly once.
We say that a pair of students is in conflict if they gave each other different assessments. Let D be the set of all possible values of the total number of conflicts. Prove that ∣D∣≥3n with equality if and only if the group can be partitioned into two subsets such that each student is separated from all of his friends.
graph theorycombinatorics