1
$\begingroup$

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.

Thanks in advance,

$\endgroup$
2
$\begingroup$

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\}\}$.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – user160738 May 5 '15 at 10:01
  • $\begingroup$ Thanks a lot, I'm amazed at how you could come up with this! $\endgroup$ – user160738 May 5 '15 at 15:20
  • $\begingroup$ @user160738 Actually I didn't have a rigorous path to make trial, but I notice Dirac's theorem... $\endgroup$ – Salomo May 5 '15 at 17:16

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.