Using a greedy algorithm to find a cut S which at least half of the edges cut

Question

Let $G$ be an undirected graph.

Find a greedy algorithm that finds a cut $S$ which at least half of the edges cut.

I tried to think about something like choosing the vertex with the highest degree, add it to $S$, remove it from the graph and then repeat this process until I'm done.

However, this is nothing more than a guess and I could not prove it.

I tried to think of the problem in another way - removing no more than half of the edges in the graph until I get a bipartite graph, but finding the cycles takes too long.

Online solutions to this problem included using random algorithms - something we haven't learned in the course where I was handed this question. Other solutions were not clear to me (including one that was posted on this site), or seemed too complicated for the course level.

Could someone provide guidance please?

Answer 1

List the vertices in some order, $v_1,\ldots,v_n$. Put $v_1$ in an arbitrary side of the cut. For each of the vertices $v_2,\ldots,v_n$, put it in the side of the cut which maximized the number of edges cut (only counting edges involving vertices which have already been processed). Since there are only two sides, each time you cut at least half the edges.