1
$\begingroup$

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)?

Improve this question
$\endgroup$
1
  • $\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
    Commented Mar 23, 2017 at 13:16

1 Answer 1

Reset to default
3
$\begingroup$

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}$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .