Задача 25.

* (теорема Холла) В некой компании $n$ юношей. При каждом $k=1$, $2$, ..., $n$ для любых $k$ юношей в этой компании найдется не менее $k$ девушек, знакомых хотя бы с одним из рассматриваемых $k$ юношей. Можно ли просватать всех юношей за знакомых девушек? Является ли это условие необходимым? Иными словами, верно ли, что в двудольном неориентированном графе (с $n$ вершинами в первой доле) существует паросочетание размера $n$ тогда и только тогда, когда для каждого набора из $k$ вершин первой доли с ними соединены хотя бы $k$ вершин второй доли?