6.18 In a tennis club, 20 members have been scheduled for 14 singles matches, where each member participates in at least 1 match. Prove that in this arrangement, there must be 6 matches between 12 different players.
Problem 1023
Official solution
[Proof 1] Let the participants in the -th match be denoted as , and define
If a subset contains pairs of participants where all participants are distinct, then is called a "good subset" of . Clearly, such good subsets exist and there are only finitely many of them. Let one of the largest good subsets be , with the number of its elements being . Clearly, it suffices to prove that .
Since is a maximal good subset, the participants who do not appear in have not played against each other. Since each participant has played at least one match, each of these participants must have played at least one match against the first participants. Therefore, in addition to the matches in , there must be at least more matches, meaning the total number of matches is at least . Since the total number of matches is 14, we have , which solves to .
[Proof 2] Use 20 points to represent the 20 members of the club, and connect two points with a line segment if the corresponding two members have a match scheduled. Thus, we obtain a graph with 20 vertices and 14 edges.
For any vertex in the graph, the subgraph consisting of and all vertices connected to by a path is called a connected component. By the given information, each vertex belongs to exactly one connected component, and each connected component contains at least one edge.
Let the graph have connected components. Since in each connected component, the number of edges is at least the number of vertices minus 1, the total number of edges in the graph is at least the total number of vertices minus , i.e., . Solving this, we get .
Taking any 6 connected components from the graph and selecting one edge from each, the 6 edges correspond to 6 matches involving 12 distinct participants.