Вот, итак, действительно связность с самого начала можно было не требовать, а теорему-то по-прежнему надо доказывать. Итак, теперь давайте доказывать теорему. Ну, товарищи, я, конечно, много пафоса навожу, на самом деле теорема исключительно простая. Я сейчас какое-то время пожую, конечно, так чтоб всем было все понятно. Но в действительности, теорема эта практически легкое упражнение, которое можно было бы задать на дом слушателям. Иногда я так делаю, но здесь не тот случай и стиль мы соблюдем. Итак, давайте возьмем наш граф, тот самый, в котором n вершин и в котором степень каждой вершины не меньше чем n/2. Так я что-то не то написал, да? Количество ребер мы не знаем, нет, количество вершин мы знаем, количество вершин равняется n, и степень каждой вершины не меньше, чем n/2. Вот тот самый граф возьмем и рассмотрим в этом графе самую длинную простую цепь, любую. Самую длинную простую цепь. Может быть она не единственная, конечно, но вот мы возьмем любую из самых длинных простых цепей и рассмотрим ее. Давайте обозначим так как-нибудь вершины этой цепи x1, x2, ..., xm. Это любая самая длинная, самая длинная простая цепь в графе G, [ПИШЕТ НА ДОСКЕ] простая цепь в графе G. Мы не знаем, конечно, как устроено m. Априори мы не знаем, мы можем только предполагать что-либо. Но очевидно, совершенно ясно, что m точно не больше, чем n. Вот это совершенно понятно. Конечно, если в графе n вершин, то самая длинная цепочка, даже самая длинная цепочка точно имеет не больше, чем n вершин внутри себя. Цепь-то простая, она там никак себя не пересекает, поэтому ясно, что m не превосходит n. Замечательно. Так, теперь давайте сделаем следующее. Докажем, докажем, что существует среди вот этих вот вершин x1, x2, ..., xm, существует такая вершина xi, что, ну, скажем, xi соединена ребром с xm, а xi + 1 — с x1. Вот докажем, что существует среди вершин x1, ..., xm такая вершина xi, что эта вершина соединена ребром с последней, а следующая за ней внутри этой цепочки вершина xi + 1 в свою очередь соединена с вершиной x1. Но это тоже очень просто. Давайте рассмотрим для этого, так докажем, да, вот сейчас мы рассмотрим для этого множество индексов, рассмотрим множество индексов, номеров вот этих вот вершин. Ну, какое-нибудь такое, скажем, 1, 2, ..., m − 1. И вот в этом множестве выделим 2 подмножества, то есть рассуждать на самом деле будем очень похожим образом на то, как рассуждали вот на этой части рассуждений, когда замечания доказывали. Значит, давайте рассмотрим вот это множество и выберем в нем 2 подмножества очень простых, выберем в нем 2 следующих подмножества, следующих подмножества. [ПИШЕТ НА ДОСКЕ] Так, I1, I (большое) 1, по определению, это подмножество, состоящее из всех индексов i вот отсюда вот, то есть из всех индексов i, которые не превосходят m − 1, таких, что пара xi, xm принадлежит множеству ребер нашего графа. Ну, выглядит достаточно формалистично, а смысл на самом деле исключительно простой, мы просто смотрим какие вершины с номерами от 1 до m − 1, какие вершины xi с номерами от 1 до m − 1 соединены ребром с последней вершиной. Думаете, таких может вообще не быть? А вот фигушки. На самом деле... смотрите какая красота, ведь это же самый длинный путь в нашем графе, самая длинная цепочка, длиннее не бывает. Но тогда это означает, что если мы возьмем вершину xm, вот эту самую, с которой мы смотрим соседей, да, внутри нашей цепи, возьмем вершину xm, так у нее все соседи, все соседи этой вершины находятся внутри этой же цепи, потому что если бы был хоть один сосед извне этой цепи, у нас получилась бы более длинная цепь. Еще раз, это самая длинная цепь. Поэтому когда вы берете вершину xm, вы не можете себе даже представить такого, это действительно не так, чтобы существовала какая-то еще одна вершина, связанная ребром с вершиной xm и при этом не принадлежащая этой цепочке. Вот такая ситуация, такой быть не может. Это удлиняет нашу цепь. Такой длинной цепи нету, это-то была самая длинная, так быть не может. Поэтому все соседи вершины xm находятся среди x1, ..., xm − 1, то есть среди вершин вот с этими номерами. Но мы знаем по условию теоремы, что таких соседей у каждой вершины, в том числе, конечно, и у m-той, не меньше чем n/2. Поэтому мы сразу можем сказать, что мощность множества I1 точно не меньше чем n/2. Вот мы взяли множество I1, которое состоит из соседей вершины xm, находящихся внутри цепи, выяснили, что а других-то соседей у этой вершины и быть не может, потому что иначе это будет не самый длинный путь, не самая длинная цепь, но и поняли тем самым, что мощность этого множества I1 никак не меньше чем n/2. Но вот я долго болтаю, а обещал-то я 2 следующих множества, а у меня пока 1. Давайте определим множество I2 как множество таких индексов i, опять же в пределах от 1 до m без 1, для которых x1 соединено ребром с xi + 1 в нашем графике. Хе! Друзья, так ведь тут жизнь устроена точно так же, как в случае с множеством I1. Ведь опять же все соседи вершины x1, все соседи вершины x1, они точно находятся среди вершин x2, ..., xm, потому что опять же, если бы был хоть один сосед у этой вершины вне нашей цепи, то цепь удлинилась бы. А это самая длинная цепь. Итак, все соседи x1 находятся среди вершин x2, ..., xm, но если мы берем i в пределах от 1 до m − 1, то i + 1, внимание, товарищи, это очень ответственный момент, если i находится в пределах от 1 до m − 1, то i + 1 находится в пределах от 2 до m. То есть, как раз в тех пределах, в которых, как мы только что выяснили, живут все соседи вершины x1, в пределах от 2 до m. Таким образом, мы получаем, что мощность вот этого замечательного множества I2 это фактически количество соседей вершины x1, все эти соседи находятся внутри нашей цепи, и этих соседей, как мы знаем по условию теоремы, не меньше, чем n/2. Видите, у нас действительно получилось 2 множества, каждое из них состоит из не менее чем n/2 элементов, и при этом оба этих множества, товарищи, находятся в множестве от 1 до m − 1, являются его подмножеством.