Гамильтонов путь - могу ли я покрыть ребро дважды, если каждая вершина может быть покрыта только один раз?

Question

Из этого вопроса - Разница между гамильтоновым путем и эйлеровым путем, каждый гамильтонов путь не является эйлеровым путем. Как я могу покрыть каждую вершину ровно один раз и пересечь ребро дважды?

Answer 1

Вы можете фактически покрыть все вершины, не пересекая каждое ребро, например, чтобы покрыть все K4 (полный граф из 4 вершин), вам нужно только пересечь 3 ребра. Но он имеет 3 * (3+ 1)/ 2 = 6 ребер. Более того: каждый узел имеет степень 3, поэтому у него нет ни эйлерова траектории, ни схемы.