why does this argument in proof of cheeger's hold?

Question

$$ \lambda \geq \frac{ \sum_{(i,j)\in E} [(u_i-u_j)^2 + (v_i-v_j)^2]}{ \sum_i d_i(u_i+v_i)^2 }$$

And then they say since $$\frac{a+b}{c+d} \geq \min \{\frac{a}{c}, \frac{b}{d}\}$$ it suffices to show that $$\frac{ \sum_{(i,j)\in E} (u_i-u_j)^2}{ \sum_i d_i u_i^2 }\geq \frac{h^2_G}{2}$$ where $h_G$ is the Cheeger constant.

Now here are my questions...

I don't understand why $$\frac{a+b}{c+d} \geq \min \{\frac{a}{c}, \frac{b}{d}\}$$ is true nor do I see why this implies we can just show $$\frac{ \sum_{(i,j)\in E} (u_i-u_j)^2}{ \sum_i d_i u_i^2 }\geq \frac{h^2_G}{2}.$$ To further elaborate, how is it true that $$\frac{ \sum_{(i,j)\in E} (u_i-u_j)^2}{ \sum_i d_i u_i^2 } \leq \frac{ \sum_{(i,j)\in E} (v_i-v_j)^2}{ \sum_i d_i(2u_i v_i + v_i^2) }$$ and thus $$\frac{ \sum_{(i,j)\in E} [(u_i-u_j)^2 + (v_i-v_j)^2]}{ \sum_i d_i(u_i+v_i)^2 }\geq \frac{ \sum_{(i,j)\in E} (u_i-u_j)^2}{ \sum_i d_i u_i^2 }$$ because these would need to hold in order to apply $\frac{a+b}{c+d} \geq \min \{\frac{a}{c}, \frac{b}{d}\}$ to begin with.

Answer 1

Hints

• In order to prove that $\frac{a+b}{c+d}\geq min \left\{\frac{a}{c},\frac{b}{d}\right\} $, you can assume that: $\frac{a}{c}\geq \frac{b}{d}$ which signifies that $ad\geq bc$ and this implies $ad+bd\geq bc+bd$ hence $\frac{a+b}{c+d}\geq\frac{b}{d} $
• Because $y_i=u_i+v_i$ and $u_iv_i=0$ we have $(u_i+v_i)^2=u_i^2+v_i^2$ , so you just forget that $u_iv_i=0$

Hope this clarifies your problems.