2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Take three copies of $K_4.$ In each copy choose one edge and subdivide it, making it a path of length $2.$ Take a new vertex and join it to the three subdivision points. The result is a cubic graph on $16$ vertices, in which the longest paths have $11$ vertices. $\endgroup$ – bof Apr 26 '18 at 23:27
  • $\begingroup$ @bof Incredible, thanks! Was there some systematic way you produced this? $\endgroup$ – Lorenzo Najt Apr 26 '18 at 23:32
  • 1
    $\begingroup$ In lieu of an explanation from bof, I'll provide a confabulation. Dropping the finiteness assumption, we may be led to consider the 3-regular tree. It is evident that this graph doesn't have a Hamiltonian path, since any fork we take prevents a Hamiltonian path from visiting the rest of the graph. We try to imitate this idea in a finite graph: we start with a claw graph, and then try to attach finite graphs to the leafs of the claw in order to recover 3-regularity. Now we are looking for a finite graph which is 3 regular except at one point of degree 2. $\endgroup$ – Lorenzo Najt Apr 27 '18 at 3:54
  • 1
    $\begingroup$ The simplest 3 regular graph is $K_4$. Instead of making vertex have one fewer degree, to get a node of degree 2 it is easier to split an edge, as bof did. Indeed, this would work with any 3 regular graph. $\endgroup$ – Lorenzo Najt Apr 27 '18 at 3:54
3
$\begingroup$

@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.

$\endgroup$
  • 1
    $\begingroup$ Using Nauty, there are no examples with fewer than 16 vertices, and this example is the unique one on 16 vertices. (I uploaded a drawing of the graph here: i.stack.imgur.com/zuZFm.png) $\endgroup$ – Rebecca J. Stones Apr 28 '18 at 3:40

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.