# Partitioning the vertices of the graph

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.

• Section 3 of this paper would be useful sciencedirect.com/science/article/pii/0012365X78901474 Oct 23, 2017 at 10:38
• What is your question? Do you want us to verify your answer? Then give it to us. Oct 23, 2017 at 15:04

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

$$\alpha(V_1,V_2):=\color{red}{d_2}\cdot\mathrm{edges}(\color{blue}{V_1})+\color{blue}{d_1}\cdot\mathrm{edges}(\color{red}{V_2})$$

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.