Теория графов и комбинаторика

Если в У ИМ9ЮТ0Я повторякщиеоя вершины, поступим о ниш так жй до тех пор, пока не получим (iT-i/T ) - маршЕут беэ повторяпцйхоя вершин, т . е . простую {'О'-'Ы )-цепь, Очав!1дно, что описанный процэоо будет конечным л силу конечнооти поола- доватвльноотиyt . Доказательство леммы 3 . 1 иллюст^-аруат рйо.3.2, на котором маршрутуИ показан сплошной линией, а- маршрут V - пунктиром. Лемма 3 . 2 . Кратчайший {1Г~ ЬТ ) - маршрут( И Т ) явля­ ется простой цепью. Это утвэрждениа неторвдстввяно следует из лемглн 3 . 1 , Лемма 3.3.' Из лккЗогс цикла ррафа (? г-^жно выделить проо- •"ой цикл. Доказательство. Цикл. Тс1'да либо он сам является простым цюшом, либо имеет две сов­ падающие вершиныг Во BToiKJM случае, так же, как при докаэательотва леммы 3 . 1 , отроим новый mr j i ; V Повторим этот процвоо для цикла У и т . д . до тех пор, пока :.Э получим цикл, вое вершины которого, кроме крайних, различны, т . е . простой цикл. Лемма Э.4. Любой цию. графа можно прадотавить как оЗъеди- нениа реберко-непвреоакающихоя ( т . е . не имаадих общих ребер) простых циклов. Докадательог..о. Требуемое представление исходного v^via можно 1гол}"Шгь, ВНД0ЛЛЯ из овгс простые циклы так, как это сде­ лано кри доказательстве леммы 3 . 3 . Лятта 3 . 5 . Любой замснутый маршрут графа нечетной длины содерхит простой цикл нечетной длины. Локазательотво. П у с т ь - замкнутый марйфут нечетной длины ) . Так же, как при докаэатвльотве ла ты 3 . 3 , выделим из него замккутие марш­ руты Г " > п , ) Один йз них имеет нечетную длину. 1овторяя даш нех-'о описанный процаоо и т . д . , получим замкнутый маршрут нечетной 30