In worst case, it is a complete graph and have to visit every edge

So, space complexity will be $\binom{v}{2}=\frac{v(v-1)}{2}=\theta \left ( v^{2}\right )$

So, space complexity will be $\binom{v}{2}=\frac{v(v-1)}{2}=\theta \left ( v^{2}\right )$