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

Is it true that, there exists a subset $M\subseteq V$ such that, for every $v\in M$, ${\rm deg}_M(v)\leq 3$, and for every $v'\in V\setminus 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 $v\in 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 $v\in 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.

  • $\begingroup$ And of course the same argument shows that, for any nonnegative integer $d$ and any finite graph $G=(V,E)$, there is a set $M\subseteq V$ such that $M=\{x\in V:|N(x)\cap M|\le d\}$. Is this also true for infinite graphs? $\endgroup$ – bof Nov 23 '18 at 5:49
  • $\begingroup$ @bof Hard to tell... Of course, when we have some sort of compactness principle, we can reduce the question to the finite case, but what would you do in the case of the unit distance graph for the points in $\mathbb R^n$, for instance? $\endgroup$ – fedja Nov 23 '18 at 22:19
  • $\begingroup$ At least it's true for locally finite graphs, by compactness. Right? $\endgroup$ – bof Nov 24 '18 at 12:46
  • $\begingroup$ The unit distance graph on $\mathbb R^n$ is easy. The cases $n=0$ (finite graph) and $n=1$ (locally finite) are trivial. For $n\ge2$ an easy transfinite construction (with the axiom of choice of course) gets us a set $A\subset\mathbb R^n$ such that $|N(x)\cap A|=0$ for $x\in A$ while $|N(x)\cap A|=|\mathbb R|$ for $x\in\mathbb R^n\setminus A$. $\endgroup$ – bof Nov 27 '18 at 6:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.