Алгоритм решения задачи на графе

Задача: Дано N колец сцепленных между собой. Удалить минимальное количество колец так, чтобы получилась цепочка.

Допустим есть такой исходный граф.

После выполнения программы должны получить такой граф, то есть необходимо избавиться от циклов внутри графа, ветвлений (в вершину входит максимум 1 дуга и выходит максимум 1 дуга).

Граф может быть направленным или ненаправленным(не имеет значения). Граф может быть представлен в виде матрицы инцидентности, смежности или списка ребер.

Я не могу правильно составить алгоритм решения данной задачи и как лучше представить граф в программе(реализовываю на python). Есть пара общих идей на основе того, что нашел в интернете и литературе:

• Выполнить поиск самого длинного пути в графе(с помощью DFS или BFS), чтобы знать приблизительное минимальное количество вершин, которое можно откинуть
• Использовать алгоритм поиска циклов в графе и выполнить удаление вершины внутри него для исключения цикла (Если подскажите алгоритм поиска циклов, буду благодарен)
• Сейчас граф представляю как матрицу смежности, которую превращаю в список смежности для каждой вершины.

Хотелось бы узнать алгоритм решения этой задачи и как лучше представить граф непосредственно в программе(описание структуры данных).