Худущий случай раскраски ребер простого графа

[2old]

Пронумеруем ребра, затем проходим ребро за ребром и красим каждое новое ребро в цвет, не использованный среди покрашенных «соседей» этого ребра. Пусть максимальная степень вершин в графе $G$ равна $\Delta$.

Какая гарантированная верхняя оценка на число используемых цветов у такого алгоритма построения рёберной раскраски?

Как бы я порядок нумерации не менял, не получается найти случай хуже чем $\Delta+1$. Но правильный ответ $2\Delta-1$, не могу понять как он получается. Точнее, $2\Delta-1$ это может быть столько соседних ребер у ребра. Но что заставляет этот алгоритм красить их все в разные цвета не могу понять.

[iancaple]

Описанный Вами алгоритм оставляет слишком много свободы:выбирается произвольно ребро для раскраски, цвет выбирается произвольно из возможных. Поэтому не удивительно, что первые шаги раскраски он может пройти настолько неловко, что данных $2\Delta -2$ цветов ему может не хватить.
Например $\Delta =4$, рассмотрим бипирамиду из тетраэдров АВCD, ABCE,+ребро DE, которое окажется последним закрашенным, а дано всего 6 цветов 1,2,3,4.5.6. Красит AD=1,BD=2,CD=3,AB=3,AC=2,BC=1, а дальше алгоритм ведет себя не оптимально, мы ж ему это позволили, AE=4,BE=5,CE=6, ну и последнее ребро DE нельзя покрасить ни в один из 6ти цветов, только поэтому и должно быть 7 цветов.

[2old]

iancaple
понятно, спасибо