Если я правильно понял, то нужно реализовать полный обход графа с бэктрэкингом, то есть пройтись по всем существующим рёбрам графа. Давненько такими задачками не занимался и что-то не припомню стандартного алгоритма, скорее всего точно такого и нет. Но можно модифицировать какой-нибудь из агоритмов обхода (в глубину/ширину) или придумать что-нибудь своё.
Общая идея такова: при переходе от одной вершины к другой помечаем соответствующее ребро как пройденное или убираем его из множества рёбер графа. При этом запоминаем пройденный путь и удалённые рёбра для возможности отката (backtracking). Цель достигнута (найден один из путей построения графа), когда множество непройденных рёбер будет пустым. Далее откатываемся на шаг назад, восстанавливаем удплённые дуги графа и пробуем найти другой путь и т.д. до окончания полного перебора вариантов. В завасимости от условий задачи, вероятно, нужно будет проделывать обход из каждой вершины т.к. при этом результирующие пути будут другими (смещёнными на какое-то количество шагов относительно ранее найденных).
Алгоритм, на первый взгляд, получается достаточно нетривиальным. Вероятно, есть и более простое и элегантное решение, но "умная мысля", как известно... Чтобы придумать (если надо), что-нибудь поэффективнее, надо немного повариться в ткого рода задачках, вспомнить студенчество :)

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

Кстати, можно ещё посмотреть BGL (C++ Boost Graph Library)
http://www.rsdn.ru/res/book/cpp/bgl.xml
Может там что-то похожее реализовано.

Библиотека довольно обширная, на изучение может уйти немало времени, но если дальше придётся работать с графами, то польза будет. А если задача решается из чисто любопытского интереса, то быстрее будет своё решение наваять.

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