Создаешь новый граф без дуг, но с тем же количеством вершин. Затем добавляешь одну дугу, если она не создает цикл.
Как распознать цикл: завести массив Mark[1..кол-во вершин], это будет массив "меток" вершин.
1) Сначала Mark[i] = i для всех i от 1 до кол-ва вершин
2) Выбираем новое ребро в том случае, если "метки" вершин, которые оно соединяет, разные. Пусть они равны, например, k и m.
3) Теперь нужно заменить по всему массиву все встречающиеся в нем элементы равные k, на m. Можно переходить снова к шагу 2.
4) Закончить, когда весь массив Mark будет заполнен одинаковыми элементами
(подробнее, как искать циклы, можно посмотреть в книге Окулова, глава Алгоритмы на графах, раздел "Каркас минимального веса. Метод Краскала". Фактически тебе нужно построить этот каркас, но не обязательно минимального веса. Книгу можно скачать на
http://pascal.net.ru)