# An example of connected graph with vertices having at least 3 degree, but non-hamiltonian?

The question is:

Does there exist a simple connected undirected graph $G$ with $7$ vertices with minimal degree $3$ but does not contain any hamiltonian cycle?

I've been trying to find an example for quite long time, but I still cannot think of one. The restriction "minimal degree 3" is giving me an headache, since I can always find a graph with no-hamiltonian cycle with "almost minimal degree 3", but whenever one edge is added so to satisfy the condition, it becomes hamiltonian...

So the question comes. Is there even a single graph with above properties? Maybe I am being a bit un imaginative, but I've found questions about finding non-hamiltonian graphs with certain properties quite hard so far.

It would be great if you could explain your strategy too with an example, since I seem to lack what is needed in this kind of exercise: I can't get the "feel" of it.

Let us take two copies of $K_4$, then contract one vertex from each copy.
More precisely, $G=(V,E)$, where $V=\{1,\dots,7\}$, $E=\{\{u,v\}\mid u\neq v, u,v\in\{1,2,3,4\}\}\cup\{\{u,v\}\mid u\neq v, u,v\in\{4,5,6,7\}\}.$
If we require additionally that it has no cut-vertex, we can consider $G=(V,E)$, where $V=\{1,\dots,7\}$, $E=\{\{1,2\},\{2,3\},\dots,\{5,6\},\{6,1\}\}\cup\{\{1,3\},\{2,4\},\{3,6\}\}\cup\{\{1,7\},\{3,7\},\{5,7\}\}$.
• Thanks, that works since any hamiltonian cycle must pass through center vertex twice, which is not allowed. This is not part of question, but is there still other example if we add the condition that graph is still connected whenever we remove a vertex from the graph? So your example does not satisfy this, since if we remove center vertex graph is $K_3 \cup K_3$. – user160738 May 5 '15 at 10:01