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

Question

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

Answer 1

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