# tough inequality for a graph theory problem

I am stuck at a step in a graph theory problem. I have to prove that $$\frac{d\cdot(d-1)^k}{(d-2)} \leq d^k$$ for $d,k \geq 3$. Here $d$ actually refers to degree of a graph and $k$ the radius.

The inequality does not work for $d, k < 3$. how to prove this kind of inequality for a particular range?

-
The degree of the graph? Every vertex may have a different degree. Or is this supposed to be a regular graph? – Nate Eldredge Aug 19 '13 at 2:16
sorry.i was talking about maximum degree – Neel Choudhury Aug 19 '13 at 2:38

You can rearrange the inequality as

$$\left(\frac{d-1}d\right)^k\le\frac{d-2}d\;,$$

which in turn can be rewritten as $$\left(1-\frac1d\right)^k\le 1-\frac2d\;.$$ Since $0<1-\frac1d<1$, we have

$$\left(1-\frac1d\right)^k\le\left(1-\frac1d\right)^3\;,$$

for $k\ge 3$, so it suffices to show that $$\left(1-\frac1d\right)^3\le 1-\frac2d$$

for $d\ge 3$. Now

$$\left(1-\frac1d\right)^3=1-\frac3d+\frac3{d^2}-\frac1{d^3}\;,$$

so we’re done if we can show that

$$\frac3{d^2}-\frac1{d^3}\le\frac1d\;.$$

This is equivalent to $3d-1\le d^2$, which is certainly true for $d\ge 3$.

-
Thank you so much – Neel Choudhury Aug 19 '13 at 2:38
@Neel: You’re very welcome. – Brian M. Scott Aug 19 '13 at 2:45