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?