А то уже готово.
Для возможности решения задачи «с параллельными ребрами» <проще всего> можно повторно включать номер вершины в 'список связанных вершин' и вместо <встроенной> функции (remove) использовать <собственную> функцию (REMOVE_FIRST), которая исключает из данного списка 'seq' только первый экземпляр данного элемента 'elem' (если они там присутствуют).

(defun REMOVE_FIRST (elem seq)

 (if seq

  (if (equal (car seq) elem)

   (cdr seq)

   (cons (car seq) (REMOVE_FIRST elem (cdr seq))))))

Функция (F) теперь определяется следующим образом:

(defun F (Graph &optional (Stack (cons (caar Graph) nil)) (Result nil))

 (if Stack

  ((lambda (curr_vertex)

    ((lambda (curr_record)

      (if (cdr curr_record)

       ((lambda (next_vertex)

         (F

          ((lambda (new_Graph)

            ((lambda (next_record)

              (subst (REMOVE_FIRST curr_vertex next_record) next_record new_Graph))

             (assoc next_vertex new_Graph)))

           (subst (REMOVE_FIRST next_vertex curr_record) curr_record Graph))

          (cons next_vertex Stack)

          Result))

        (cadr curr_record))

       (F Graph (cdr Stack) (cons curr_vertex Result))))

     (assoc curr_vertex Graph)))

   (car Stack))

  Result))

Добавим ребро между вершинами 1 и 2 в первый из ранее представленных графов (при этом получаются две вершины нечетной степени!, так что нам просто повезло, что функция начинает поиск эйлерова пути с одной из них)
(F '((1 2 2 6)(2 1 1 3 5 6)(3 2 4 5 6)(4 3 5)(5 2 3 4 6)(6 1 2 3 5)))
Однако задача создания «оболочки» по-прежнему важна.
Но относительно кёнигсбергских мостов препод прав - они «параллельны», но и это нам на руку - не важно, по какому именно «мосту» идти от одной вершины к другой, если «мостов» несколько, так что и именовать их нет нужды.