where the degree of a node in one partition is the number of edges incident to the node in that partition. Show that the solution obtained (S1,S2) by algorithm Local Search MAX-CUT is at least 1/2 of the optimal

Given an undirected, connected graph G (V, E), partition the nodes in V into two disjoint sets S and S2 (i.e., S1 nS2) such that the number of edges between the nodes in Si and S2 is maximized. In the following, there is a simple greedy algorithm of finding such a partition for this problem. Local Search.MAX-CUT(G(V, E)) 1 (Si, S2)any partition of the set V; /* Let din(v) and doui(v) be the degrees of node v in its own partition and another partition; if ES then else endif 2 while 3u E V s.t. din(u > dout(u) do move node u to S2; move node u to Si endwhile 6 Return (S, S2, Given an undirected, connected graph G (V, E), partition the nodes in V into two disjoint sets S and S2 (i.e., S1 nS2) such that the number of edges between the nodes in Si and S2 is maximized. In the following, there is a simple greedy algorithm of finding such a partition for this problem. Local Search.MAX-CUT(G(V, E)) 1 (Si, S2)any partition of the set V; /* Let din(v) and doui(v) be the degrees of node v in its own partition and another partition; if ES then else endif 2 while 3u E V s.t. din(u > dout(u) do move node u to S2; move node u to Si endwhile 6 Return (S, S2