I have an question about graphs. Is there any graph in which there is no cycle, but it has a Hamiltonian circuit? I think there isn't such a graph.
Am I right?
Thanks for your answer in advance.
$\endgroup$ 01 Answer
$\begingroup$A graph without any cycles can't contain a Hamiltonian circuit since a Hamiltonian circuit is a cycle.
If you meant Hamiltonian path instead of Hamiltonian circuit, then there is a solution. A Hamiltonian path is itself an example of a graph that trivially contains a Hamiltonian path but does not contain a cycle.
If you were to add any edge to a Hamiltonian path, you would immediately introduce a cycle and the resulting graph wouldn't satisfy your requirements anymore. So, the only type of graph that contains a Hamiltonian path but no cycles is a simple path.
$\endgroup$ 2
