In the Land of Linguists live \(m\) people, who have opportunity to speak \(n\) languages. Each person knows exactly three languages, and the sets of known languages may be different for different people. It is known that \(k\) is the maximum number of people, any two of whom can talk without interpreters. It turned out that \(11n \leq k \leq m/2\). Prove that then there are at least \(mn\) pairs of people in the country who will not be able to talk without interpreters.
In a graph \(G\), we call a matching any choice of edges in \(G\) in such a way that all vertices have only one edge among chosen connected to them. A perfect matching is a matching which is arranged on all vertices of the graph.
Let \(G\) be a graph with \(2n\) vertices and all the vertices have degree at least \(n\) (the number of edges exiting the vertex). Prove that one can choose a perfect matching in \(G\).