Это неверно.

Строим 2 графа - обычные треугольники. Потом берем, и соиденяем эти 2 треугольника одной вершиной.

Получм что-то похожее, на бабочку для костюма.

Выйдет 4 вершины со степенью 2 и вершину, которая является соединением треугольников, у которой степень 4. Убирая ее получим несвязный граф, состоящий из двух одинаковых частей: 2 соединенные вершины