граф Петерсена

[StudentSimferopol]

Доказать, что в графе Петерсена нет гамильтонова цикла, но в графе,полученном из него удалением одной вершины, имеется гамильтонов цикл.

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

[svv]

В Википедии написано:

Цитата:

Сильно регулярен и рёберно регулярен, то есть, выбрав вершину или ребро, можно отобразить граф на себя, переведя выбранный объект в любую вершину (ребро).

Это значит, что все вершины равноценны, и достаточно рассмотреть удаление одной (любой).

Или... Вы какой перебор имели в виду?

[StudentSimferopol]

Собрал в кучу , все что прочитал. (многое копипаст)

У графа Петерсена нет никакого гамильтонова цикла C, описываем 3-регулярные графы с десятью вершинами, которые действительно имеют гамильтонов цикл и показывают, что ни один из них не граф Петерсена, находя цикл в каждом из них, который короче чем любой цикл в графе Петерсена. Любой гамильтонов 3-регулярный граф с десятью вершинами состоит из цикла с десятью вершинами C плюс пять аккордов. Если какой-либо аккорд соединяет две вершины на расстоянии два или три вдоль C друг от друга, граф имеет с 3 циклами или с 4 циклами, и поэтому не может быть графом Петерсена. Если два аккорда соединяют противоположные вершины C к вершинам на расстоянии четыре вдоль C, есть снова с 4 циклами. Так как у графа Петерсена есть обхват пять, это не может быть сформировано таким образом и не имеет никакого гамильтонова цикла.