Можно ли единожды обойти все вершины связного неориентированного графа и вернуться в начальную вершину?
Можно ли обойти все вершины графа и вернуться в начальную?
Можно.
Судя по описанию, вам нужен Гамильтонов путь.
Эта задача NP-полна - следовательно, простого и быстрого алгоритма человечеству не известно. Можно делать полный перебор с отсечениями и эвристиками. Какие-нибудь методы имитации отжига или генетические алгоритмы могут работать быстрее, но это не точно и нужно долго и мучительно ковыряться, что бы оно заработало.