Разбиение вершин графа на два подмножества

[VoprosT]

Дан граф с кол-вом вершин $n, n \geqslant 6$. Известно, что $\deg(v)=3, \; \forall v \in V$, $V$ - множество вершин графа. Докажите, что вершины графа можно разбить на два непустых подмножества так, что в каждом подмножестве любая вершина соединена ребром как минимум с двумя другими вершинами из этого же подмножества.

Всё, что удалось вытянуть из условия: из того, что степени каждой вершины равна $3$ следует, что в графе есть цикл(в любой компоненте связности нет висячей вершины), а так же то, что подмножества из разбиения одновременно содержат чётное или нечётное число вершин (поскольку $\left\lvert E \right\rvert = \frac{3}{2}n$).

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

[ИСН]

Вот, допустим, граф $K_{3,3}$. Как его разбить?