Problem 2, Homework 5

In part a) of problem 2, $C_{uv} \leq |E|$ is not achievable; you might want to prove $C_{uv} \leq 2|E|$ instead. Consequently, your upper-bound in part b) should be $2|V||E|$ (we don't mind if you show us a $4|V||E|$ bound), and hence the probability in part c) will be something like 3/4 (instead of 7/8). Thanks Yiming for pointing this out.


If you are going to use the theorem $C_{uv} = R_{uv}\times C$ (where $R_{uv}$ is the effective resistance between $u$ and $v$), keep in mind that in this case $C = \sum_{i} C_i = 2\times \sum_{e} C_e$.