Why does a 2-colourable simple graph with n nodes have no more than $(n^2/4)$ arcs?

Question

Why does a 2-colourable simple graph with n nodes have no more than $(n^2/4)$ arcs?

I would really appreciate for any kind of explanations.

Answer 1

By 2-colorable graph I think is meant a coloring of nodes, so that any edge is between nodes of different colors, i.e. a bipartite graph. Consider how to partition the $n$ nodes so that the number of edges by connecting all possible pairs will be largest.

Roughly we divide the nodes into two equal groups. In the simplest case $n$ is even and we get $n/2$ in each part. The most edges possible would be exactly the figure $(n/2)^2$ that appears in your question.

---

Let's work out how to maximize edges that cross from one part to the other (of a bipartite graph). In total we have $n$ nodes. Suppose we put $x$ nodes in one part and $n-x$ in the other, then make all the possible $x(n-x)$ edges between them.

What value of $x$ will maximize $x(n-x)$? First we check the boundary conditions, i.e. if $x=0$ or equivalently $x=n$, then we get no edges (one of the two parts is empty).

So consider the intermediate values $0 \lt x \lt n$ and extend the counting to a continuous function of $x$ on the open interval $(0,n)$, i.e. $f(x) = x(n-x) = nx - x^2$. Calculus tells us the maximum occurs at the critical point, $f'(n/2) = 0$, of this parabola. Note that $f(n/2) = (n/2)^2$.

This is then an upper bound on the number of edges in a bipartite graph with $n$ nodes, but it can only be attained when $n$ is even. If $n$ is odd, we can't quite split the nodes in two equal parts, and the best we can do is split them $\frac{n-1}{2}$ and $\frac{n+1}{2}$.

However we were only asked to show that $n^2/4$ is an upper bound (no more than this many edges or arcs), not to give the details of when the upper bound is sharp (can be met exactly).