Ответ:

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

У каждой из 6 вершин по 4 ребра.