40 узлов кажется выполнимым. Вы выбираете 40 из 60 ребер для включения.
Давайте попробуем поиск в глубину.
Для начала выберите вершину V. Вам нужно будет исключить ровно один из 3 ее инцидентных ребер. Попробуйте эти 3 варианта по одному. Когда вы выбираете ребро для исключения, вы принудительно включаете 4 ребра. После этого мы будем называть вершины исключенного ребра «used».
Если бы вы могли повторить этот процесс 10 раз, вы бы выбрали все 40 ребер, ища только 3 ^ 10 (59049) возможностей. Конечно, у вас закончатся «изолированные» вершины после того, как будет определено достаточное количество ребер.
Но теперь у нас есть идея для алгоритма. На каждом шаге попробуйте выбрать вершину с наименьшим количеством «используемых» соседей. На самом деле, выбор вершины с 2-мя использованными соседями является наилучшим, поскольку используемый край является принудительным. Я не уверен, что выбор вершины с 1 или 0 использованными соседями является следующим лучшим. Попробуйте оба способа! (И 3 используемых соседа указывают на неудачный поиск)
Когда мы закончим выбирать ребра, проверьте, образуют ли они один цикл.
У вас есть несколько примеров графиков? Я мог бы попробовать простую реализацию.