2
$\begingroup$

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.

$\endgroup$
2

1 Answer 1

0
$\begingroup$

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})$$

instead.


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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .