[Math] (finite, connected) 3-regular graph with no Hamiltonian path

graph theory

Is there a (finite, connected) 3-regular graph with no Hamiltonian path?

Comments:

1) The Petersen graph has no Hamiltonian cycle, but it does have a Hamiltonian path.

2) In lieu of https://en.wikipedia.org/wiki/Lov%C3%A1sz_conjecture, the counter example (if it exists) is probably not vertex transitive.

3) If $|G| = n$, and if there is a independent set of size $ > n/2$ then there is no Hamiltonian path. However, no example can be constructed using this observation, because of: Maximum independence number of any $d$-regular graph on $v$ vertices

I'm also curious about the $k$-regular case. (For $k \geq 3$.)

Best Answer

@bof constructed this nice small example with 16 vertices:

O---O   O---O
|\ /|   |\ /|
| O |   | O |
|/  |   |  \|
O---O   O---O
     \ /
      O
     /
O---O
|\  |
| O |
|/ \|
O---O

If you want a better connected example (such as one without bridges), you can construct it by

  1. Take your favorite sufficiently large well-connected cubic graph.
  2. Choose a vertex and replace its 3 neighbors by Tutte fragments, such that the three "compulsory" edges point towards your chosen vertex. This forces any Hamiltonian path in the graph to have an endpoint in one of the Tutte fragments.
  3. Repeat step 2 with two other center vertices.

Now you have a graph with three disjoint sets of three vertices that each must contain one of the endpoints of any Hamiltonian path. But that is clearly impossible.

Related Question