Can I get help with this? Problem $1($Max Cut$).$ Given an undirected and unweighted graph $G=(V,E),$ the maximum

cut problem asks for a partition of $V$ into sets A and $B($partition meaning $AB=\{\}$ and $AB=V)$

so that the number of edges between these sets $($that is$,$ with one endpoint in A and the other in

$B)$ is maximized. This problem is NP$-$hard. Give a polynomial time approximation algorithm that

achieves an approximation ratio of $2($that is$,$ the algorithm should compute a partition with at least

$\frac{1}{2}$ times as many crossing edges as the optimal partition$).$ Prove that your algorithm achieves

this approximation ratio, and state the running time of your algorithm. $[$ textitHint: Consider a

greedy algorithm. You may find the handshaking lemma useful in your analysis: ${\displaystyle \underset{\text{v}\text{i}\text{n}\text{V}}{\overset{?}{}}}d(v)=2|E|$

where $d(v)$ is the degree of $v.$