Htykuut

Take an undirected graph $G=(V,E)$. For any subset $Msubseteq V$, we define ${rm deg}_M(v)=|{kin M:(v,k)in E}|$, namely, the number of neighbors of $v$ in $M$.

Is it true that, there exists a subset $Msubseteq V$ such that, for every $vin M$, ${rm deg}_M(v)leq 3$, and for every $v'in Vsetminus M$, ${rm deg}_M(v')geq 4$?

Note that, some obvious cases. If nobody are friends, we can simply take $V$ to be the entire set. Similarly, if $G$ is fully connected, then any $4-$element subset work. I tried to reason in the following way, take a maximal (in the sense of cardinality) $M$, such that, for every $vin M$, ${rm deg}_M(v)leq 3$. Now, for any point outside, if it has $geq 4$ neighbors, we are done. If not, then there are points in $M$, which are neighbors of $v$, such that, their in$-M$ degree is precisely $3$, but this did not lead me to anywhere.

Let us consider all sets $M$ with $d_M(v)le 3$ for all $vin M$ (I'll write $d$ instead of $rm{deg}$) and choose the set that maximizes
$$
|M|-frac 14 E(M)
$$
where $E(M)$ is the number of edges between the vertices in $M$.
Assume that there is a vertex $w$ with $d_M(w)le 3$. We can try to add it to $M$ but it may spoil some its neighbors in $M$ (those that had degree $3$ in $M$ already). Then we may just delete the bad neighbors one by one as long as their degree is $4$ (after the first deletion we can improve other vertices too, so we may delete only part of spoiled neighbors and the rest may get their low degree recovered). If we do $k$ deletions, we get $|M|to |M|+1-k$, $E(M)to le E(M)+3-4k$, which certainly increases the functional by at least $frac 14$. Thus the trivial algorithm (add a vertex and remove the resulting conflicts, if any, one by one) works and achieves the desired result in $4|V|$ steps at the worst.