Давайте построим это доказательство, проведём это доказательство с помощью индукции по числу юношей. То есть по размеру условной верхней доли, доли V1. Давайте, индукция по мощности множества V1. Как обычно, что такое база индукции? Ну база индукции тут совсем тривиальная. База индукции такая: значит, мощность V1 = 1, а мощность V2 — какая угодно, то есть мы здесь ничего не говорим про мощность V2. Вторая-то доля — множество девушек — может быть какой угодно. Значит, вот давайте возьмём одну вершину в этой условно верхней доле. И вот здесь куча каких-то девиц на выданье. Сколько хотите. Что означает условие Холла в этом случае? А мы, конечно, предполагаем, что условие Холла выполнено. Но оно тривиальным образом означает следующее: понятно, что в множестве вершин, которое состоит всего лишь из одного элемента, есть только одно содержательное подмножество. Там говорится про любое подмножество, но тут есть только одно содержательное подмножество: она же сама, вот эта вершинка. И условие Холла в этом случае говорит, что количество соседей просто этой вершины в нижней доле, то есть количество девушек, которых готов рассматривать в качестве потенциальной супруги вот этот молодой человек, ну, оно точно не меньше единицы, потому что мощность этого множества, как мы сказали, равняется единице. То есть вниз идёт хотя бы одно ребро, ну может быть, несколько там, я не знаю, но хотя бы одно. Ну и всё. Вот вам паросочетание и образовалось. Ни с кем конфликтовать не нужно. Очевидно, что в этом случае условие Холла сразу гарантирует наличие паросочетания, покрывающего все вершины верхней доли. Ну потому что просто эта вершина одна, и чего уж тут особенно болтать? Вот интереснее, конечно, проделать шаг индукции. Ну сейчас это сделаем. Ну что ж, коль скоро база индукции у нас есть, давайте сделаем предположение. То есть давайте предположим, что для каждой верхней доли, размер которой не превосходит заданного какого-то числа k, и для абсолютно любой нижней доли, если выполнено условие Холла, то всё в порядке — паросочетание есть. Ну давайте я это напишу. Предположим, что при мощности V1, не превосходящей какого-то k, ну, например, при мощности V1, не превосходящей единицы, в базе индукции мы уже это сделали. Ну вот давайте предположим, что при V1, не превосходящим какого-то k, и при любой доле V2, если выполнено условие Холла, то паросочетание есть. Если выполнено условие Холла, то паросочетание есть, которое покрывает все вершины V1. Ну, понятно вот, то самое, которое мы ищем, паросочетание есть. Докажем, что то же самое верно и для любого V1 мощности k. Докажем то же самое, если... Ой, k! k + 1, конечно. Для k мы уже доказали. Это мы предполагаем, оговорился. Докажем то же самое, если мощность V1, конечно же, равняется k + 1. Возьмём совершенно произвольный набор молодых людей, имеющий мощность k + 1, абсолютно произвольный набор девушек. Предположим, что у нас выполнено условие Холла для этих двух долей, и будем доказывать, что в этом случае тоже обязательно найдётся паросочетание, которое покрывает все вершины условной верхней доли, то есть вот этой доли V1. Так, рассмотрим два случая. Давайте я сразу обозначу, какие два случая, ну и последовательно мы их рассмотрим. Значит, случай 1 такой: для любого A, которое является собственным подмножеством множества V1. Видите, я здесь подчеркнул, что оно с V1 не совпадает. Оно вложено в V1, но заведомо с ним не совпадает. И вот в этом случае я говорю, что подмножество собственное. То есть не совпадающее с ним. Так вот, для любого собственного подмножества... Ну хорошо, да, давайте, я хотел немножко в другом порядке, но не имеет значения. Для любого собственного подмножества A из V1 мощность A строго меньше, чем мощность окрестности. Это чуть более сильное условие, нежели условие Холла. В рамках условия Холла мы предполагаем, что здесь стоит нестрогое неравенство, то есть количество юношей не превосходит количество девушек, из которых они готовы выбирать в совокупности. Вот. А здесь мы предполагаем нечто более сильное. Мы предполагаем, что мощность A строго меньше, чем мощность NG от A. То есть понятно, что в рамках условия Холла такое может быть выполнено, а может и не быть. Ну и случай 2, естественно, дополнительный. Случай 2, естественно, является отрицанием случая 1. То есть существует какое-то собственное подмножество множества V1. Существует некоторое подмножество, которое не совпадает со всем V1, и у которого мощность в точности равняется мощность множества NG (A). Вот я утверждаю, что можно так разделить на две ситуации, чтобы в каждой из них затем завершить с помощью предположения индукции наше общее рассуждение, наше доказательство теоремы Холла.