Problem 3
Let be a positive integer. people take part in a party. For each pair, either the two people are acquainted or they are not. What is the maximum possible number of pairs that are not acquainted but have a common acquaintance among the participants?
Step 3 of 6: Join components
Detailed analysis
If two components have no acquaintance edge between them, adding one such edge creates no new counted cross-pair, so it cannot decrease the objective. Thus an extremal graph may be assumed connected.