Так из этого в свою очередь вытекает следующее замечательное соображение: что значит что оно является собственным подмножеством? Оказывается, это означает вот что. Давайте я это прямо в виде еще одного утверждения сформулирую и скажу так: κ (G), ну то есть наша вершинная связанность, которая присутствует в формулировке самой теоремы. κ (G) не превосходит мощности множества Nw (G). Мощность множества Nw (G) не меньше чем κ или наоборот κ не больше чем мощность множества Nw. Доказательство, доказательство. Доказательство очень простое. Давайте удалим из графа G вершины множества Nw (G). Вот их всех удалим. Ну мне, честно говоря, не хочется перерисовывать в очередной раз рисунок, рисунок у меня есть. Вот. Давайте на него посмотрим и возрадуемся, потому что все будет совершенно понятно. Видите мы удаляем вот отсюда из этого цикла вершины множества Nw (G), они все находятся в этом цикле. Правильно? Но при этом мы с вами знаем, вот оно следствие, что мы удаляем не все вершины этого цикла, а только некоторую их часть. Удалили, а часть вершин осталась. Потому что, повторяю, Nw (G) не совпадает с множеством вершин нашего цикла, а удалили мы только Nw (G), удалили и часть вершин осталась. С другой стороны, смотрите ведь Nw (G) — это множество всех соседей, вот этого W в исходном графе G. Значит когда мы эти вершины удалили, у W больше соседей не осталось. То есть W — это точная связная компонента и при этом здесь есть еще какие-то вершины, которые с ней очевидно не связаны. Но значит граф развалился. Давайте я это все запишу. Удалим из G вершины множества Nw (G). С одной стороны мы удаляем всех соседей, мы удаляем всех соседей, по определению просто, множества W. Но теоретически может так получиться, что удалили мы их, ну и осталось только множество W и ничто не мешает ему быть связным. Правильно? Мы удалили всех соседей. С другой стороны мы знаем, что некоторые вершины цикла, некоторые вершины исходного цикла при этом удалении удалены не будут, вершины цикла удалены не будут. [ПИШЕТ НА ДОСКЕ] Иными словами останется множество W, изолированное такое, у которого больше соседей нет и останутся вот эти вот вершины цикла которые не удалены. Это означает, что граф развалится на несколько компонент. На несколько компонент. То есть мы уже показали, что вот столько вершин точно можно удалить из нашего графа, дабы в результате граф развалился. Ну из этого конечно и следует, что минимальное количество вершин, удаление которых приводит к уничтожению связности графа, оно не больше чем мощность вот этого множества. Это минимальное количество вершин, удаление которых приводит к развалу графа, а это количество вершин, про которые мы точно знаем, что их удаление приводит к развалу графа. Ну, значит, минимальное не превосходит вот этого и утверждение полностью доказано. Замечательное утверждение: κ не превосходит мощности Nw (G). Но это еще отнюдь не все. Вот, товарищи, осознается как? Или повторить что-нибудь? Ну не знаю, я думаю что достаточно, я в общем так прожевал подробно это утверждение. Давайте еще попробуем выжать какие-нибудь соки из предыдущего утверждения. То есть из утверждения о том, что нет соседних вершин в множестве Nw (G). Я думаю что нам сейчас это удастся. Это мы должны помнить: соседних вершин в множестве Nw (G) нет. Давайте введем в рассмотрение некое новое множество M, давайте его обозначим M. Это будет множество таких x(i + 1), для которых xi принадлежит Nw (G). Вот что это такое нарисовано? Значит, у нас есть вершины цикла, которые принадлежат множеству Nw (G). И, внимание, мы знаем, мы знаем, что следующие за ними вершины в Nw (G) не попадают. Потому что мы доказали, что соседних вершин цикла в множестве Nw (G) нет. Если xi там присутствует, то x(i + 1) присутствовать там же никак не может. Таким образом мы получаем, исходя из утверждения, которое мы доказали, что M, пересеченное с Nw (G) — пусто. В множестве M нету вершин, которые бы входили вот это, в это Nw (G). С другой стороны, за счет вот этого утверждения, мы получаем, конечно, что мощность M, которая равняется мощность Nw (G). Ну, понятно, мощности-то у них совпадают. Мы просто для каждой вершины отсюда берем следующую за ней. Мощности у них совпадают и раз вторая из них ≥ κ, то и первая тоже ≥ κ (G). Это вот мы только что доказали. Вот. У нас есть такое множество M и его мощность достаточно большая. И вот сейчас будет предкатарсис, в некотором смысле. Сейчас я наконец сформулирую некое утверждение, которое продемонстрирует нам связь между этой злополучной κ и не менее злополучной α, то есть числом независимости. Наконец-то мы сейчас дойдем до сути, докопаемся до существа дела.