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.
Graph Theory – Is There a Graph with All Vertices Having Degree 3 or Greater That Doesn’t Have a Hamiltonian Path?
discrete mathematicsgraph theoryhamiltonian-path
Related Solutions
For context: a result of Pósa says that a random graph with $C n \log n$ edges already contains a Hamiltonian path with probability tending to $1$, and here we have a uniformly random graph (with $\frac{n^2}{4}$ edges on average). So we can be fairly wasteful.
As far as an algorithm goes, we can take the algorithm used to prove Dirac's theorem. The hypotheses of that theorem don't hold here, but the algorithm will still work with high probability. The strategy is this:
- Pick a path greedily: start at a vertex $v_1$, pick a vertex $v_2$ it is adjacent to, then pick a vertex $v_3$ adjacent to $v_2$, and so on. Repeat until you get stuck.
- Turn the path into a cycle: if it has endpoints $v_1$ and $v_\ell$, find adjacent vertices $v_i$ and $v_{i+1}$ on the path such that $v_{i+1}$ is adjacent to $v_1$ and $v_i$ is adjacent to $v_\ell$. Then the cycle is $v_1, \dots, v_i, v_\ell, \dots, v_{i+1}, v_1$.
- Turn the cycle into a longer path: if $v_{\ell+1}$ is a vertex not on the cycle, find a vertex $v$ on the cycle adjacent to $v_{\ell+1}$, and take the path starting next to $v$, going around the cycle, and then going to $v_{\ell+1}$.
- Repeat steps 2 and 3 until the path contains all the vertices.
All of these steps are quite likely to work individually. The problem is that to analyze how likely they are to work as a whole, we'd have to check edges of the graph multiple times, which doesn't preserve independence.
So instead, we will write our uniformly random graph $G$ as the union of graphs $G_0, G_1, \dots, G_{10 \log n}$, where $G_0$ contains each edge independently with probability $\frac14$, and $G_1, \dots, G_{10 \log n}$ contain each edge independently with probability $p$, chosen so that $\frac34(1-p)^{10 \log n} = \frac12$. Then the union will contain each edge with probability $\frac12$, so it will be the uniformly random graph. If we solve for $p$, we get $p = O(\frac{1}{\log n})$, but all we'll really need is for $p$ to be asymptotically bigger than $\frac{1}{\sqrt n}$.
Then I claim that:
- A greedy path chosen in $G_0$ will reach length $n - 5\log n$ with very high probability.
- Doing step 2 of the algorithm in any of the $G_1, \dots, G_{10 \log n}$ will work with very high probability.
- Doing step 3 of the algorithm in any of the $G_1, \dots, G_{10 \log n}$ will work with very high probability.
Then we can just look at graphs $G_0, G_1, \dots$ sequentially as we go through the algorithm. This preserves independence, and if the edges we need will be in the graph $G_i$ we're looking at, they will be in the union $G$.
For the first claim: the probability that a greedy path will get stuck while there's still $5 \log n$ vertices to pick from is $(\frac34)^{5\log n} = n^{-5\log \frac43}$, so the probability is at most $n^{1 - 5\log \frac43} \approx n^{-0.43}$ that it ever gets stuck.
For the second claim: we have at least $\frac n2$ options for vertices $v_i$ and $v_{i+1}$, and each one works with probability $p^2$. The probability that none of them work is $(1-p^2)^{n/2} \le e^{-p^2n/2}$, which approaches $0$ as $n\to \infty$. (This is where we want $p \gg \frac{1}{\sqrt n}$, so that the exponent goes to $-\infty$ as $n\to\infty$. We actually want a bit better than that, because we want all $O(\log n)$ of these steps to work, so the probability should go to $0$ faster than $\frac{1}{\log n}$. But our $p$ is actually quite a bit larger than $\frac{1}{\sqrt n}$, so we have that wiggle room.)
For the third claim: we have at least $\frac n2$ options for the vertex $v$, and each works with probability $p$. The probability that none of them work is $(1-p)^{n/2} \le e^{-pn/2}$, which approaches $0$ as $n\to \infty$.
Checking if a given graph has a Hamiltonian path is hard; however, cooking up examples of graphs that definitely don't have Hamiltonian paths is much easier. For example, if the graph didn't have to be planar, then you could take the complete bipartite graph $K_{6,8}$. This does not have a Hamiltonian path because any path alternates sides of the graph, but this bipartite graph is unbalanced so you would run out of vertices on the side with $6$ vertices before visiting all of the vertices on the other side.
There is a planar example that fails to have a Hamiltonian path for a similar reason: the skeleton graph of the rhombic dodecahedron. This polyhedron is constructed by putting square pyramids on the faces of a cube in such a way that the sides of adjacent pyramids line up and we end up with six diamond-shaped faces.
The graph is a subgraph of $K_{6,8}$: the vertices that were vertices of the cube are only adjacent to the vertices that form the tips of the pyramids, and vice versa. So it's bipartite and not Hamiltonian. It's planar and $3$-connected because it's the skeleton graph of a polyhedron: the polyhedral graphs are precisely the $3$-connected planar graphs.
Finally, here is one way to solve this problem that probably goes against the spirit of the exercise but is very much in the spirit of doing independent work in graph theory. Go to the House of Graphs and run the following search:
- Require a specific (numeric) value for an invariant: "Number of vertices equal to 14" and "Vertex Connectivity greater than or equal to 3"
- Only consider certain classes of graphs: "Planar", "Bipartite", and NOT "Traceable".
This will give you exactly one result, which is the rhombic dodecahedral graph.
Best Answer
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):
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.