Пути в графе константной длинны.

[makak]

Здравствуйте! У нас есть граф решетка 5*5=25 вершинах. Всего он содержит 40 ребер. Можно ли покрыть это граф 5 путями длины 8 так, что бы мы в итоге прошли все ребра? Аналогично с 8 путями и длинной 5?

На первое ответ нет, доказывается от сюда:
Пусть G — граф, в котором 2N вершин имеют нечетную степень. Тогда множество ребер G можно покрыть N реберно-простыми путями.

Второе никак не могу доказать. Может есть какие нибудь теоремы?

[DeBill]

makak
Не понял логику...
1. Из приведенного Вами утверждения ответ "нет" на 1) не следует.
2. Зато следует ответ "да" на 2).
3. Но ответ "нет" на 1) все-таки следует - однако не из сформулированног Вами (и Вики) утверждения - а из того, что там реально имелось в виду (вторая половина утверждения грит ".... , и нельзя - меньшим кол-вом путей.")
4. Если с 2) остались проблемы (в смысле - как покрыть) - просто возьмите док-во из Вики, и проведите его конкретно для Вашего графа.

[makak]

DeBill
Спасибо за помощь, с первым пунктом я разобрался.
Но мне никак не дается второй пункт, как вы думаете, граф все таки можно или нельзя покрыть таким числом путей?
По идее, из 8 путей длинны 5, мы можем образовать Эйлеров цикл(т.е. словить противоречие как при доказательстве первого пункта не получается).

Не актуально, можно, и я понял как.