The Max-Cut problem asks to find a subset $S$ of the vertices of a graph (with $m$ edges) such that the number of edges from $S$ to it's complement is as large as possible. The size $|M|$ of a max cut is the number of such edges.
It is easy to prove using a probabilistic argument or a greedy algorithm that $|M| \geq m/2$. I have a few questions regarding the optimality of this bound:
Do there exist graphs where the max cut is exactly $m/2$. If it is, is it still optimal when we restrict the set of graphs we are looking at?
For instance, I think if the number of vertices is $2n$, $|M| \geq \frac{n}{2n -1}m$. I got this by looking at a few small examples. Is this true and is it easy to prove(it seems like it should be but I have not had much luck)?
Is there a much better bound for some other class of common graphs?(Bipartite graphs give a bound of $m$ trivially...)
For every graph with $m$ edges, the size of the max cut must be greater than $\frac{m}{2}$. To see this, consider the well-known randomized algorithm for the max cut problem (i.e., each vertex has a probability of 0.5 to be in $S$). The expected number of edges in the output is exactly $\frac{m}{2}$. However, there is a nonzero probability that the output contains less than $\frac{m}{2}$ edges (e.g., all vertices in the graph are in $S$, which leads to zero edge in the cut). This implies that there is a nonzero probability that the output contains more than $\frac{m}{2}$ edges. Thus, the max cut must have more than $\frac{m}{2}$ edges.