So consider a maximal matching. Suppose it contains $t$, with $t\le 5$ edges. Then there are $20-2t$ vertices not in this matching. Since the matching is maximal, those vertices span no edges. However we know that every vertex has a positive degree, so the number of edges from the remaining vertices is greater than or equal to $20-2t$. This requires a total that is greater than or equal to $(20-2t)+t=20-t\ge 15$ edges, which is too many.

we use graphs.we take a maximal matching.if possible suppose we have p[<=5]edges.it is easy to see that there are 20-2p who are not in this matching. all vertices have degree >=1.the vertices who are not in the matching do not span edges. so, we need at least (20-2p)+p=20-p >=15 edges , which is a contradiction as only 14 games are there.

We can represent this as a graph of $20$ vertices and $14$ edges. For the sake of contradiction, assume in any set of $6$ edges, there is at most $11$ vertices. Thus, the sum $S$ of the number of vertices over all sets of $6$ edges is \[S \leq \binom{14}{6}\times 11.\] Now each edge is represented $\binom{13}{5}$ times over all the sets of $6$ edges. Every edge has two vertices, and therefore $S=\binom{13}{5}\binom{14}{1}\cdot 2$. Thus, \begin{align*} \binom{13}{5}\binom{14}{1}\times 2&\leq \binom{14}{6}\times 11 \\ \cancel{\frac{13\times 12\times 11\times 10\times 9}{5\times 4\times3\times2\times1}\times\frac{14}{1}}\times 2&\leq \frac{\cancel{14\times13\times12\times11\times10\times9}}{6\times\cancel{5\times4\times3\times2\times1}}\times11 \\ 2&\leq \frac{11}{6}, \end{align*} a contradiction, therefore there must exist some set of $6$ edges containing $12$ vertices and we are done.

Consider an arbitrary graph $G$ with $20$ vertices and $14$ edges. Separate it into $k$ connected components of $v_1,v_2,\dots,v_k$ vertices and $e_1,e_2,\dots,e_k$ edges respectively. Note that $e_i\geq v_i-1$, so $14=\sum e_i\geq \sum (v_i-1)=20-k\implies k\geq 6$. Since the problem statement demands that every connected component contains an edge, we conclude. $\Box$

Consider a graph $G = (20, 14)$. From the degree sum formula, $\sum_{v \in V} \deg(v) = 2 \cdot E = 28$ where $V$ is the set of vertices. Suppose $k$ of the vertices have degree $1$. Then it follows that $\sum_{v\in V} \deg(v) = 28 \ge k + (20-k)\cdot 2 \Rightarrow k\ge 12$. Thus, at most we have $8$ vertices with degree that is greater than $1$. If we ignore $8$ such edges associated with these vertices then we have at least $6$ edges left and the degree of all remaining vertices is less than or equal to $1$. Hence, this is the $6$ games that occurs within $12$ distinct players, as desired.

MithsApprentice wrote: The 20 members of a local tennis club have scheduled exactly 14 two-person games among themselves, with each member playing in at least one game. Prove that within this schedule there must be a set of 6 games with 12 distinct players. Pick a maximal matching of $G$ with $m$ edges. Each edge of $G$ emanates from a vertex of this matching, so since each player plays at least once, we have $20-2m \ge 14-m \implies m \ge 6$ as desired.

JSGandora wrote: We can represent this as a graph of $20$ vertices and $14$ edges. For the sake of contradiction, assume in any set of $6$ edges, there is at most $11$ vertices. Thus, the sum $S$ of the number of vertices over all sets of $6$ edges is \[S \leq \binom{14}{6}\times 11.\]Now each edge is represented $\binom{13}{5}$ times over all the sets of $6$ edges. Every edge has two vertices, and therefore $S=\binom{13}{5}\binom{14}{1}\cdot 2$. Thus, \begin{align*} \binom{13}{5}\binom{14}{1}\times 2&\leq \binom{14}{6}\times 11 \\ \cancel{\frac{13\times 12\times 11\times 10\times 9}{5\times 4\times3\times2\times1}\times\frac{14}{1}}\times 2&\leq \frac{\cancel{14\times13\times12\times11\times10\times9}}{6\times\cancel{5\times4\times3\times2\times1}}\times11 \\ 2&\leq \frac{11}{6}, \end{align*}a contradiction, therefore there must exist some set of $6$ edges containing $12$ vertices and we are done. I think that this solution is incorrect because when you get that $S=\binom{13}{5}\binom{14}{1}\cdot 2$ you are not counting the same thing as here \[S \leq \binom{14}{6}\times 11.\].At first you are counting sum of all cardinalities of covering sets with $6$ edges ,and on later sum of degres of all covering sets(with $6$ edges).By covering set i mean the set of vertices such that ends of all chosen edges are in that set and no other edge is. By the way $S\leq\binom{13}{5}\binom{14}{1}\cdot 2$

anantmudgal09 wrote: MithsApprentice wrote: The 20 members of a local tennis club have scheduled exactly 14 two-person games among themselves, with each member playing in at least one game. Prove that within this schedule there must be a set of 6 games with 12 distinct players. Pick a maximal matching of $G$ with $m$ edges. Each edge of $G$ emanates from a vertex of this matching, so since each player plays at least once, we have $20-2m \ge 14-m \implies m \ge 6$ as desired. It should be $m\le6$!

tc1729 wrote: So consider a maximal matching. Suppose it contains $t$, with $t\le 5$ edges. Then there are $20-2t$ vertices not in this matching. Since the matching is maximal, those vertices span no edges. However we know that every vertex has a positive degree, so the number of edges from the remaining vertices is greater than or equal to $20-2t$. This requires a total that is greater than or equal to $(20-2t)+t=20-t\ge 15$ edges, which is too many. The number of edges associated with the remaining vertices might not be at least $20-2t$ as some of the edges may have both endpoints among the remaining vertices.

Arslan wrote: tc1729 wrote: So consider a maximal matching. Suppose it contains $t$, with $t\le 5$ edges. Then there are $20-2t$ vertices not in this matching. Since the matching is maximal, those vertices span no edges. However we know that every vertex has a positive degree, so the number of edges from the remaining vertices is greater than or equal to $20-2t$. This requires a total that is greater than or equal to $(20-2t)+t=20-t\ge 15$ edges, which is too many. The number of edges associated with the remaining vertices might not be at least $20-2t$ as some of the edges may have both endpoints among the remaining vertices. Hi, what you said can't occur since we can move that edge to the maximal matching set, which is contradicting the maximality

Could we just argue that a graph with $n$ vertices and $k$ connected components must have at least $n-k$ edges, so our graph $G$ must have at least $6$ connected components. Since each connected component cannot be an isolated vertex (everyone played at least a game), just pick an edge in each connected component.