Гамильтонов путь

[AndreyXYZ]

Пусть $G$ - негамильтонов граф с $n \geq 3$ вершинами, вершины $u$ и $v$ несмежны, и их соединяет совственный гамильтонов путь. Доказать, что для степеней этих вершин верно неравенство $d(u)+d(v) \leq n-1$

Подскажите хотя бы идею решения.
Я пытаюсь доказывать от противного. Если $d(u)+d(v) > n-1$, то число элементов в пересечении окрестностей $|\delta(u) \cap \delta(v)| \ge 2$. Но дальше, к сожалению, я продвинуться не могу.

Добавлено спустя 6 минут 9 секунд:

И еще вопрос. Где можно почитать про алгоритм Флери построения эйлерова цикла?