<p>There is a polynomial-time algorithm to find hamiltonian cycles in graphs where every vertex degree is at least N/2.</p>

<p>It's described in <a href="https://arxiv.org/abs/1606.03687" rel="nofollow noreferrer">"A Simple Extension of Dirac’s Theorem on Hamiltonicity" Yasemin Büyükçolak, Didem Gözüpek, Sibel Özkan, Mordechai Shalom</a>.</p>
How to find Hamiltonian Cycle in a graph using BFS? (the condition is that the graph is exactly hamiltonian)
<p>I am trying to solve the Hamiltonian Cycle problem.</p>

<p>The condition of my task is:</p>

<p>The group consists of N people. In it, everyone has exactly N / 2 friends. Friendship is symmetrical (if A is friend B, then B is friend A). One person in the group has a book (his number X), which everyone would like to read and then discuss with some of the others.</p>

<p>It is necessary to determine the method of transferring the book, in which it would visit everyone exactly once, passing only from friend to friend, and finally return to its owner.</p>

<p>That is, it satisfies the condition of the Dirac's theorem.</p>

<p>On small graphs <a href="https://www.geeksforgeeks.org/hamiltonian-cycle-backtracking-6/" rel="nofollow noreferrer">my solutions</a> works properly, but on big graphs my solution gives time limit exception.</p>

<p>Is there any method how it can be solved faster than O(n!)?</p>