Граф Петерсена и его негамильтоновость

[MestnyBomzh]

Здравствуйте! Вопрос такой: как доказать, что этот граф негамильтонов? Как я понял, проверить теорему Хватала не достаточно..Что тут нужно сделать?

[svv]

Не знаю. Но могу вывести это, опираясь на то, что хроматический класс графа Петерсена равен 4.

В графе Петерсена 10 вершин и 15 ребер. Гамильтонов цикл (если он есть) содержит 10 ребер. Раскрасим их поочередно (в порядке движения по циклу) в красный и зеленый цвет. Остальные 5 ребер, не принадлежащих циклу, покрасим в синий цвет. В каждой вершине соединяются 3 ребра. Так как каждая вершина проходится один раз, ей инцидентно одно красное и одно зеленое ребро, а также одно синее, не участвующее в обходе. Но тогда мы получим трехцветную реберную раскраску, тогда как сам Петерсен доказал, что это невозможно.

[patzer2097]

еще можете тут посмотреть topic79189.html

[MestnyBomzh]

svv в сообщении #804908 писал(а):

Не знаю. Но могу вывести это, опираясь на то, что хроматический класс графа Петерсена равен 4.

В графе Петерсена 10 вершин и 15 ребер. Гамильтонов цикл (если он есть) содержит 10 ребер. Раскрасим их поочередно (в порядке движения по циклу) в красный и зеленый цвет. Остальные 5 ребер, не принадлежащих циклу, покрасим в синий цвет. В каждой вершине соединяются 3 ребра. Так как каждая вершина проходится один раз, ей инцидентно одно красное и одно зеленое ребро, а также одно синее, не участвующее в обходе. Но тогда мы получим трехцветную реберную раскраску, тогда как сам Петерсен доказал, что это невозможно.

Спасибо, всё доступно и понятно. Вопрос только в том, что означает число 4? Количество цветов, такие что при определенной раскраске ни один не будет соприкасаться с другим?

[svv]

Да. При определении хроматического числа раскрашивают вершины, чтобы смежные были разных цветов, а при определении хроматического класса (а здесь речь о нем) — ребра. Ребра, встречающиеся в любой вершине, должны быть разных цветов. И Петерсон показал (как — не знаю), что трех цветов для ребер барона графа Петерсона недостаточно.

[MestnyBomzh]

Щас посидел, подумал...Вроде придумал другое решение: рассмотреть точку на внешнем пятиугольнике и рассмотреть два случая: удалить ребро ведущее в центр или удалить ребро идущее по внешнему пятиугольнику (их два, однако такие случаи идентичны). Далее будет ещё разветвление на два простых случая, которые ведут к не гамильтоновым циклам.

-- 23.12.2013, 02:03 --

Про разветвелния на два случая - это я, конечно, погорячился.