Итак, докажем следующее замечательное утверждение.
В w...
В Nw, извините,
от (G), вот в этом множестве соседей,
в Nw(G) нет ни в коем случае
соседних вершин цикла.
То есть мы уже знаем, что Nw(G) является подмножеством
множества вершин цикла, а теперь мы хотим доказать такое утверждение,
что в этом множестве Nw(G) соседних вершин цикла не бывает.
Ну сейчас я заново нарисую нашу картину так,
чтобы она соответствовала нынешней цели.
Докажем это утверждение.
Предположим что xi-тое
и одновременно xi +
1 принадлежат Nw(G).
Здесь надо сделать важное замечание, что когда я пишу x с индексом i + 1,
я подразумеваю, что нумерация вершин в нашем цикле в каком-то смысле циклическая.
То есть x с индексом (m + 1) — это, конечно, то же самое, что x1.
Если я прибавляю единичку к m-той последней вершине цикла,
то это подразумевается вершина x1.
Вот это надо понимать.
Ну а так мы, действительно, предполагаем,
что есть две какие-то соседние вершины цикла, которые находятся в множестве
соседок вот этой компоненты связности графа G', которую мы обозначили w.
И вот теперь я рисую картину.
Вот у меня есть x1, дальше пошла x2, и так далее.
Где-то вот тут находится xi-тое.
Вслед за ней идет xi+1 — те самые, про которые мы предположили,
что они находятся здесь, да?
Дальше идет еще что-то, ну и так далее.
Вот получается весь наш цикл.
И где-то по-прежнему живет такая вот связная компонента w.
Давайте я ее обозначу.
Есть связная компонента w.
Но, повторяю, это связная компонента графа G', не самого графа G.
Граф G связен.
Так, замечательно!
И мы, как я уже сказал неоднократно, предположили,
что вот обе эти вершины находятся среди соседей w внутри графа G.
Ну понятное дело, что это означает.
Это означает, что у xi-того есть какая-то соседка внутри w,
и у (xi + 1) тоже есть какая-то соседка внутри w.
Давайте я вот так вот для красоты нарисую, как я сейчас нарисовал.
Внимание!
Конечно, эти соседки могут оказаться одной и той же вершиной.
Ну могут оказаться.
А я нарисовал, что их две.
Ну не судите меня слишком строго,
я не готов сразу нарисовать все 10 возможных рисунков.
На самом деле (или 100, или 1000, я не знаю, сколько) на самом деле это,
конечно, не имеет никакого значения, и сейчас вы это поймете.
Важно только, что поскольку вот это множество w образует связную компоненту,
конечно, любые две его вершины соединены какой-то простой цепью.
Иначе это не была бы связная компонента.
Так, замечательно!
Смотрите, что получается.
Значит, вот у нас какая-то соседка w1,
вот какая-то соседка w2.
А получается вот что.
Ну давайте я все-таки что-нибудь на доске зафиксирую.
w1 и w2 связаны какой-то
простой цепью, простой цепью P в w.
Поскольку w — это связная компонента,
ну значит, там между любыми двумя вершинами есть какая-то цепь.
И я ее просто обозначил — вот эта цепь P, связывающая вершины w1 и w2.
Возникает совершенно замечательная вещь.
Возникает, товарищи, цикл,
длина которого на единицу больше, чем длина исходного цикла.
А какой цикл-то возникает?
Ну смотрите сюда.
Вот такой.
Шлеп!
Шлеп!
Поехали так: тык-тык-тык-тык-тык, оп!
И вернулись.
И сюда прошли по вот этой цепочке P.
Ну, я не знаю, мне как-то не хочется рисовать формально, что здесь получается.
Еще раз: прошли, скажем, из w1 в w2.
Ну если они совпадают, то просто сразу оказались в w2, никуда не пошли.
Вот так, шлеп!
Потом двинулись вот сюда.
Обошли вот так.
И вернулись в w1.
Ну я думаю, что после второй демонстрации уже совершенно понятно,
какой цикл образовался, и почему он длиннее исходного.
Вот в этом новом цикле нету ребра, которое соединяет xi и (xi + 1).
Нету!
Вот он так идет.
Видите?
Хлоп-хлоп-хлоп!
Это ребро он не затрагивает.
Нету ребра [xi; xi + 1].
Но все остальные ребра исходного цикла в нем, конечно, присутствуют.
Все, кроме вот этого выкинутого.
Зато в нем есть вот это ребро [xi + 1; w1] и вот это ребро [xi; w2].
Видите, взамен одного ребра, которое удалилось, появилось как
минимум два новых, а возможно, и еще целая куча, которая входит в цепь P.
Ну, как я уже сказал, совершенно не важно,
цепь P — это реальная цепь или это пустое множество.
В любом случае как минимум плюс 2 и минус 1.
То есть новый цикл, который в нашем предположении образовался,
действительно как минимум на одно ребро длиннее, чем цикл, который был изначально.
Но мы же предполагали, что изначальный цикл — самый длинный.
Следовательно, есть цикл,
который длиннее исходного,
и это противоречие.
...исходного, и это противоречие.
Это противоречие.
Ну, противоречие с предположением о том,
что все-таки две соседних вершины цикла присутствуют в Nw(G).
Раз это противоречие, значит, утверждение о том, что таких соседок нету,
мы доказали.
В Nw(G) нет соседних вершин цикла.
Утверждение доказано.
Какое отсюда сразу следствие?
Сразу отсюда вытекает, конечно, что Nw(G)
не совпадает с множеством x1, ..., xm.
Ну как бы оно могло совпадать, если в нем соседних вершин этого множества нет?
Конечно, не совпадает.
При этом, как мы помним, оно является подмножеством этого множества.
Ну то бишь оно является собственным подмножеством этого множества,
то есть подмножеством, которое со всем множеством никак не совпадает.