Let $G=(V,E)$ be a finite simple graph such that between any two vertices there is a path of length at most $2$, and suppose that every vertex has at least $2$ neighbors.

Does $G$ have a Hamiltonian path (by which I mean a path visiting all vertices exactly once)?

  • $\begingroup$ The suspension of a discrete space which has at least $\ 4\ $ different points (for a total of at least $\ 6\ $ vertices for the whole graph) doesn't admit any Hamiltonian path. $\endgroup$ – Włodzimierz Holsztyński Mar 23 '17 at 13:16

No. Glue a bunch of triangles together at the same vertex. For a $2$-connected example, take the previous example and add a universal vertex.

For an example that is $n$-connected take $K_{n, n+2}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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