Утверждение ложно.
Контрпример. Возьмём звезду $K_{1,4}$ (центр и 4 листа), она простая, связная и имеет нечётное число вершин $n=5$. В любой простом пути через центр можно пройти максимум от одного листа через центр к другому листу, т.е. посетить не более 3 вершин; поэтому путь, проходящий через все 5 вершин, невозможен. Более общо, звезда $K_{1,m}$ при $m\ge 3$ (соответственно $n=m+1$) не содержит гамильтонова пути. (В дереве гамильтонов путь существует тогда и только тогда, когда число листьев $\le 2$; звезда с $m\ge 3$ имеет $m>2$ листьев.)
Достаточные условия (коротко):
- Теорема Дирака: если $n\ge 3$ и минимальная степень $\delta (G)\ge n/2$, то $G$ содержит гамильтонов цикл (а значит и гамильтонов путь).
- Теорема Ора (вар.: для пути): если для всех несмежных вершин $u,v$ выполняется $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n-1$, то $G$ содержит гамильтонов путь. Доказательство варианта: добавить новую вершину, смежную со всеми вершинами $G$; полученное графу на $n+1$ вершах удовлетворяет условию Ора ${\mathrm{deg}}^{\prime }(u)+{\mathrm{deg}}^{\prime }(v)\ge n+1$, значит имеет гамильтонов цикл, удаление новой вершины даёт гамильтонов путь в исходном графе.
- Более общие критерии: теорема Шватала—Эрдёша, теорема Хватала и др. дают условия по степенному последовательностям на наличие гамильтонова цикла/пути.
Замечание о сложности: проверка существования гамильтонова пути в общем графе NP-полна, поэтому простого необходимо и достаточного критерия для всех графов не ожидается.