Partition of a graph with 2n vertices

Question

I just proved that, given a simple undirected graph $G=(V,E)$ with $n\geq 2$ vertices and $e$ edges, there exists a partition of the vertex set $V=A\cup B$ such that the number of edges in $A \times B$ is at least $e/2$. Now, on the course notes it is written that if $n=2k$ is even, than clearly the bound $e/2$ can be improved to $\frac{k}{2k-1} \cdot e$. Can anyone give me a clue about why this is "clear"? Thank you

Answer 1

I suspect that their intended proof for $e/2$ was as follows.

Choose a random partition, putting $\lfloor n/2\rfloor$ random vertices in $A$ and the remaining $\lceil n/2\rceil$ in $B$. Now for each vertex $x$, at least half of the other vertices are in the opposite set. Thus if $xy$ is an edge, the probability that $xy$ goes between $A$ and $B$ is at least $1/2$. It follows that the average number of such edges is at least $e/2$, so there must be some partition that is at least this good.

Doing it that way, if $n=2k$ then for every vertex exactly $k$ of the other $2k-1$ are in the opposite set, and you get the "clear" improvement they suggest. (You can in fact get a similar improvement for odd $n$ too, but it needs an extra step.)

Answer 2

This is a comment, but I can't fit it in a comment box.

It's clear that if $e\neq0$, there must be strictly more than half the edges in $A\times B$, but I don't see how to get the explicit bound. By construction, every vertex in $A$ has at least half its neighbors in $B$, and vice versa. Suppose that exactly half the edges of $G$ belong to $A\times B$. Then any of $A$ has exactly half its neighbors in $B$, so we can move it to $B$ without changing the number of edges in $A\times B$. We can continue in this way until $A$ is empty. Then it is still the case half the edges are in $A\times B$, so $e=0$.

So if $e\neq0$, there must be a vertex $v$ that has more than half its neighbors in the other set. If the degree of $v$ is even then it has at least two more neighbors in the other set. If the degree of $v$ is odd, then there must be at least one more vertex of odd degree. If $e_1$ is the number of edges in $A\times B$ then we see that $$e_1\geq(e-e_1)+2\implies e_1\geq{e+2\over2},$$ but that's a long way short of the "clear" bound, and it doesn't use "$n$ is even."