Задания по теории графов

[Piteryo]

Вот не приходят идеи мне к этим 2 задачкам по теории графов:
1) Доказать, что в мультиграфе всякий замкнутый маршрут нечетной длины l>=3 содержит простой цикл. Доказать, что это несправедливо для маршрутов четной длины.

мои мысли

Здесь вообще чего-то не пойму, на что влияет четность/нечетность, и с чего это маршрут обязан иметь простой цикл.

2) Пусть p(G) - наименьшая из степеней вершин графа G, не имеющего петель и кратных ребер и содержащего n вершин (n >= 2)
Доказать, что если p(G) >= (n-1)/2, то граф связен.

очевидное рассуждение

Понятно, что все оставшиеся вершины будут иметь маршрут между собой, но вот как это строго доказать понять чего-то не могу.

@темы: Теория графов, Дискретная математика

Comments

[Дилетант]

2) Лучше всего доказывать от противного. Пусть для каждой вершины выполняется неравенство p(G) >= (n-1)/2 и при этом граф имеет две компоненты связности.
В одной из компонент количество вершин будет <= n/2. А степени всех вершин >= (n-1)/2. Нужно показать, что такой граф будет иметь кратные ребра либо петли.
Понятно, что чем меньше компонента, тем больше будет кратных ребер. Поэтому рассмотрим случай, когда граф поделен на две равные части (при четном n).
Если n - четно, пусть n/2=k, тогда степени вершин >=k. Поскольку у каждой вершины ровно k-1 сосед, то следовательно есть кратные ребра или петли.
Для n нечетного похожие рассуждения.

1)

с чего это маршрут обязан иметь простой цикл.

С того, что он замкнутый. Но условие не очень понимаю.