Show that the difference of max degree and min degree is greater than or equal 2.

446 Views Asked by At

Show that if $G$ is a non regular of order $n$ and size $rn/2$ for some integer $r$ with $1 \leq r\leq n-2$, then $\Delta(G)-\delta(G) \geq 2$

Here is what I got so far. The average degree of $G$ : $\overline{d}=2 (\frac {rn}{2n})=r$

Since $\delta(G) \leq \overline{d} \leq \Delta(G)$

$\delta(G) \leq r \leq \Delta(G)$

Since $G$ is non-regular graph $\delta(G) \geq 1$, so i got

$1\leq \delta(G) \leq r \leq \Delta(G)$

Now I'm stuck.

1

There are 1 best solutions below

0
On BEST ANSWER

Just the assumption that $G$ is non-regular does not imply $\delta(G)\geq 1$ since there might be some isolated vertices. The point here is that since $G$ is non-regular, we have $\delta(G)<r<\Delta(G)$ (note the strict inequalities!).

On the other hand, $r$ is an integer...