-3
$\begingroup$

Is there a countable connected graph $G=(\omega, E)$ such that $\text{deg}(v)=\omega$ for all $v\in\omega$, but there is no Hamiltonian path in $G$?

$\endgroup$

1 Answer 1

4
$\begingroup$

Take the natural numbers as vertices and connect a pair of numbers with an edge if their difference is divisible by three. Also connect 1 with 2 and 2 with 3.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.