Is there a simple undirected graph with the following properties ?

  • Each vertex has at least degree $4$
  • Each vertex is start vertex of some hamiltonian path
  • The graph does not contain a hamilton cycle.

    Hypohamiltonian graphs (like the Petersen graph) fulfill the last two properties but I do not know if there are hypohamiltonian graphs with minimum degree $\ge 4$. Furthermore, I search a nice criterion when a graph fulfills the last two properties.


This isn't a very fulfilling answer, but it technically works. Perhaps to request a more interesting example, you could demand a 4-connected graph.

Anyway, here is the example:

  1. Start with the Petersen graph.
  2. Replace each vertex with a complete graph $K_\ell$ for some $\ell \geq 4$.
  3. Normally, each vertex of the Petersen graph has three incident edges. Each copy of $K_\ell$ will also have three additional incident edges, going to three different vertices. These additional edges will be hooked up between copies of the complete graph just like in the Petersen graph.

Call this graph $G$.

Starting at any vertex, we can always use a Hamilton path of the Petersen graph to extend to a Hamiltonian Path in $G$ (just include the extra vertices on the way). However, there is no Hamiltonian cycle. Each complete graph must be visited only once going along the cycle, since there are only three edges connecting it to the rest of the graph. Therefore, a Hamiltonian cycle of $G$ reduces to a Hamiltonian cycle of the Petersen graph, which doesn't exist.

  • $\begingroup$ Please describe your method more precise! $\endgroup$ – Peter Oct 14 '14 at 22:26

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.