Is there a graph with these properties?

Question

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.

Answer 1

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.