Упражнения

3.1. Пусть G — связный граф, имеющий вершин нечетной степени. Докажите, что множество ребер Е графа G нельзя разбить на такие подмножества что каждое образует открытую цепь в графе

3.2. Докажите, что если граф G является произвольно-эйлеровым из вершины и, то либо и — единственная точка сочленения, либо граф G не имеет ни одной точки сочленения.

3.3. Пусть G — эйлеров граф на вершинах. Докажите, что G — произвольно-эйлеров граф из одной, двух или всех своих вершин или ни из одной из них.

3.4. Докажите, что если граф G — произвольно-эйлеров из вершины v, то где — максимальная степень в графе

Рис. 3.8.

3.5. Пусть G — произвольно-эйлеров из вершины v. Докажите, что если то граф G — произвольно-эйлеров из вершины и.

3.6. Существует ли. граф, в котором эйлерова цепь является одновременно и гамильтоновым циклом? Охарактеризуйте такие графы.

3.7. Покажите, что граф на рис. 3.8 не содержит гамильтонова пути.

3.8. Пусть G — простой связный граф на вершинах. Докажите, что длина наиболее длинного пути графа G должна быть больше или равна 26 (G), где — минимальная степень вершины в графе G [3.2].

3.9. Пусть G — простой граф на вершинах. Докажите, что он содержит гамильтонов путь, если для каждой пары вершин и и у в графе G выполняется следующее соотношение:

3.10. Пусть — степени вершин простого графа, имеющего вершин. Докажите, что если то граф G имеет гамильтонов путь [3.1].

3.11. Пусть G — простой граф на вершинах и ребрах и Докажите, что граф G является гамильтоновым [3.3].

3.12. Предположим, что G — простой граф на вершинах, имеющий такие несмежные вершины и и v, что Пусть G — граф, полученный при добавлении к графу G ребра . Покажите, что граф G гамильтонов тогда и только тогда, когда граф G также гамильтонов.

3.13. Замыкание простого графа G на вершинах есть граф, полученный последовательным соединением пар несмежных вершин, сумма степеней которых не менее до тех пор, пока это возможно. Покажите, что замыкание графа является правильно определенным.

Примечание. Простым следствием упражнения 3.12 является что граф будет гамильтоновым тогда и только тогда, когда его замыкание — гамильтонов граф. Таким образом, графв—гамильтонов, если его замыкание является полным графом. Этот результат можно использовать для доказательства некоторых достаточных условий, определяющих гамильтоновы графы

3.14. Докажите, что максимальное число попарно-непересекающихся гамильтоновых циклов в полном графе равно

Примечание. Символ означает наибольшее целое число, меньшее или равное

3.15. Граф G называется гамильтоново-связным, если для каждой пары различных вершин и и v графа G существует гамильтонов -путь. Докажите, что простой граф G порядка 3 является гамильтоново-связныч, если для каждой пары несмежных вершин и у графа G выполняется следующее неравенство:

3.16. Покажите, что граф деревьев (определенный в упражнении 2.28) связного графа является гамильтоновым [3.19, 3.20].