Maximum cut optimisation
1) is easy. As you say the algorithm can perform at most $O(|E|)$ iterations. Initially $c(V_1, V_2)=0$. Each iteration, except the last, increases $c(V_1, V_2)$ by at least $1$. The claim follows since $c(V_1, V_2) \le |E|$.

2) Suppose that, for some $v \in V_1$, $|\alpha(v)| &gt; |\beta(v)|$ Then moving $v$ from $V_1$ to $V_2$ increases the value of $c(V_1, V_2)$ by $|\alpha(v)|$ and decreases it by $|\beta(v)|$, therefore $c(V_1 \setminus \{v\}, V_2 \cup \{v \}) = c(V_1, V_2) + |\alpha(v)| - |\beta(v)| &gt; c(V_1, V_2)$. This shows that  the algorithm could not have terminated. The case $v \in V_2$ is symmetric.