Let $d, d_1, d_2$ be positive integers with $d_1+d_2+1=d$. If $\Delta(G)=d$ then the vertex set of $G$ can be partitioned into sets $V_1$ and $V_2$ such that the graphs $G_i=G[V_i]$ induced on the vertex set $V_i$ satisfy $\Delta(G_i)\leq d_i$ .

I know the answer to this problem but unable to verify it.

Consider the partition $V_1$, $V_2$ for which $\alpha=d_1\cdot\mathrm{edges}(G_1) + d_2\cdot\mathrm{edges}(G_2)$ is minimal. I tried proving by contradiction by pushing a vertex of degree more that $d_1$ from $G_1$ to $G_2$ and hoped to get that $\alpha$ should decrease by atleast one.


You almost had it but you got your factors mixed up. Minimize



So if there is a $v\in V_1$ with $d_{V_1}(v)\ge d_1+1$, then

$$d_{V_2}(v)\le d-d_{V_1}(v)\le d-d_1-1=d_2+1-1=d_2.$$

So if you push $v$ to the other set $V_2$, you observe a change in $\alpha$ with value

$$\Delta\alpha=-d_2\cdot d_{V_1}(v)+d_1\cdot d_{V_2}(v)\le -d_2(d_1+1)+d_1d_2=-d_2\le 0$$

The same holds for appropriate pushes from $V_2%$ to $V_1$. The case $d_1=d_2=0$ is easy and can be solved separately. So assume $d_1>0$ or $d_2>0$ and hence pushing in at least one direction always decreases $\alpha$. Therefore we can never get stuck in a cycle and this must finally terminate.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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