Есть ли гамильтонова схема в графе по ссылке ниже?

Question

Вроде вопрос говорит на картинке в ссылке.

Есть ли hamilton circuit на графике выше?

я нашел немного hamilton path лайк:

c - b - a -j - i - h -  f - e - d - g

Но нет hamilton circuit

Я не могу добавить картинку сюда, так как stackru не позволяет мне

Answer 1

Там не может быть гамильтонов цикл.

Доказательство:

В гамильтоновом цикле каждая вершина должна быть посещена, и никакое ребро не может использоваться дважды. Таким образом, если вершина имеет степень два, оба ее ребра должны использоваться в любом таком цикле.

a, c, а также g степени два, поэтому из гамильтонова цикла следует указать путь j - a - b - c - d - g - h, Однако этот путь не содержит e но он содержит два eсоседи, b а также d, e только один оставшийся сосед, fтаким образом, нет никакого способа расширить путь до гамильтонова цикла, который содержит e, Таким образом, в графе не может быть гамильтонова цикла.