теорема Холла

Теорема о свадьбах (также теорема о мальчиках и девочках, теорема Холла) —утверждение о том, что в двудольном графе для любого натурального любые вершин одной из долей, где не превышает числа вершин доли, связаны по крайней мере с различными вершинами другой доли тогда и только тогда, когда граф разбивается на пары по первой доле. Доказана в 1935 году Филиппом Холлом.