The Petersen graph provides us with an example of an non-Hamiltonian 3-connected 3-regular graph. Are any 4-connected 4-regular graphs known to be non-Hamiltonian? What about generic $k$-connected $k$-regular graphs?
2026-04-29 08:28:42.1777451322
Non-Hamiltonian $k$-connected $k$-regular graphs ($k>3$)?
320 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
According to this paper (Regular n-Valent n-Connected NonHamiltonian Non-n-Edge-Colorable Graphs by G. H. J. Meredith) the answer is yes (by construction) for $k=4$ and $k \ge 8$ but the other cases are not shown there. You can see a nice picture of the construction (which goes via the Petersen graph) for $k=4$ on page 5.