deletions | additions       diff --git a/q4.tex b/q4.tex  index 2ce40d9..8d2dc68 100644  --- a/q4.tex  +++ b/q4.tex 
...
Let $opt$ be the optimal cost and let $B_i$ be a cut that separates city $i$ from the rest of the graph. Since each edge in the optimal solution is in 2 different components each edge must be in two of the cuts $B_i$. So that means the sum of all of the $B_i$'s must be equal to two times the optimal value.  We also know that due to our algorithm we found the min-cuts we can call $C_i$ which are smaller than $B_i$.  So the sum of all  the $C_i$s, $<=$ $C_i <=$  sum of all  the $B_i$s $B_i$, which is  $=2*opt$ So our algorithm is at most 2 times worse than the optimal solution.