Графы. зашла в тупик, почти решив задачу

решала такую задачу на графы:

В стране 77 городов, некоторые из которых соединены дорогами. При этом из любого города до любого существует путь, в котором ни один город не повторяется, а количество пройденных дорог делится на три. Какое минимальное количество дорог может быть в стране?

Мои рассуждения:

Нарисуем схему в виде графа, в котором города-это вершины, а дороги-ребра.
Так как получившийся граф связен(что видно из условия, ведь 
"...При этом из любого города до любого существует путь..."), то в нем 
заведомо минимум 76 ребер(доказывается по индукции, то есть с компонентой связности
из двух вершин должна соединяться третья, они образуют новую компоненту,
далее с ней должна быть соединена четвертая вершина и т.д.). 
Если вершин 76, то 2 вершины имеют степень 1, назовем их А и В. Но тогда
есть один, как вариант добраться до соседней с А вершиной, причем он состоит из 
1 ребра, нам такое не подходит. Аналогично опровергается возможность существования 77 ребер,
только здесь мы берем единственную вершину со степенью 1. 

Но теперь я зашла в тупик, я не знаю, существует ли пример на 78 вершин, или есть опровержение... Думаю, если примера на 78 ребер нет, то на 79 ребер он существует точно... Помогите пожалуйста!!! Заранее спасибо за помощь:)