Minimum number of K_3 under some constraints.
Source: 2018 China Southeast MO Grade 10 P7
July 31, 2018
combinatoricsgraph theory
Problem Statement
There are participants attended a meeting. Each two of them shook hands once or not. A total of handshakes occured in the meeting. For any two participants who have shaken hands, at most among the rest participants have shaken hands with exactly one of these two persons. Define a friend circle to be a group of participants in which each person has shaken hands with the other two. Find the minimum possible value of friend circles.