Is there a graph with all vertices having degree 3 or greater that doesn't have a hamiltonian path?

Is there an example of a simple, undirected graph with all vertices having degree 3 or greater that doesn't have a hamiltonian path? I've seen this question appear in the title of this post, but then the author proceeds to talk about cycles and chords rather than hamiltonian paths. I haven't been able to come up with any simple, undirected graphs where all the vertices are of degree 3 or greater and there doesn't exist a hamiltonian path.

Solution 1:

Yes, even if we further restrict (as you probably had in mind) to connected graphs. One example is the complete bipartite graph $K_{3, 5}$, whose partitions have $3$ and $5$ vertices. (In fact, this is the smallest example; see below.)

More generally, since the sequence of vertices of any Hamiltonian path must alternate between the $2$ partitions, any bipartite graph wherein one partition has at least $2$ more vertices than the other admits no Hamiltonian path.

On the other hand, a theorem of Rahman-Kaykobad---related to but strictly stronger than Ore's Theorem---states that (borrowing from Wikipedia):

A [connected,] simple graph with $n$ vertices has a Hamiltonian path if, for every non-adjacent, [distinct] vertex pairs the sum of their degrees and their shortest path length is greater than $n$.

By definition the path length between any two distinct, nonadjacent vertices is $\geq 2$, and in our setting each degree is $\geq 3$, giving a sum of at least $3 + 3 + 2 = 8$ for each pair of vertices. So, the theorem implies that every graph with fewer than $8$ vertices but with all vertices having degree $\geq 3$ admits a Hamiltonian path. In particular $K_{3, 5}$ has the smallest vertex count of any example.

More generally, a graph whose vertices all have degree $\geq m$ but no Hamiltonian path must have at least $2 m + 2$ vertices, and the complete bipartite graph $K_{m, m + 2}$ furnishes a minimal example.