Olympiad combinatorics

A triangle-free graph cannot let two adjacent vertices share a common neighbor, so their combined degree is tightly capped by $n$; splitting the vertices into two roughly equal groups and connecting every cross pair saturates this cap everywhere at once, which is why the balanced complete bipartite graph is the extremal example.

We induct on $n$. For $n \le 2$ the claim is trivial since $\lfloor n^2/4 \rfloor \ge 0$ and any graph on at most 2 vertices has at most 1 edge.

Suppose the statement holds for all triangle-free graphs on fewer than $n$ vertices, and let $G$ be triangle-free on $n$ vertices. If $G$ has no edges the bound holds trivially, so assume $G$ has an edge $uv$. Since $G$ is triangle-free, $u$ and $v$ have no common neighbor, i.e. $N(u) \cap N(v) = \varnothing$.

Because $N(u)$ and $N(v)$ are disjoint subsets of the $n$-vertex set, $\deg(u)+\deg(v) = |N(u)|+|N(v)| = |N(u) \cup N(v)| \le n$.

Remove $u$ and $v$ from $G$ to get a triangle-free graph $G'$ on $n-2$ vertices. Every edge of $G$ is either the edge $uv$, an edge from $u$ or $v$ to the rest, or an edge of $G'$; counting carefully, $e(G) = e(G') + \deg(u) + \deg(v) - 1$ (the $-1$ corrects for the edge $uv$ being counted once inside $\deg(u)+\deg(v)$ but it is not an edge of $G'$).

By the induction hypothesis $e(G') \le \lfloor (n-2)^2/4 \rfloor$, so $e(G) \le \lfloor (n-2)^2/4 \rfloor + n - 1$. A direct computation gives $(n-2)^2/4 + n - 1 = n^2/4 - n + 1 + n - 1 = n^2/4$, and checking the even/odd cases of $n$ separately shows $\lfloor (n-2)^2/4 \rfloor + n - 1 \le \lfloor n^2/4 \rfloor$ exactly. Hence $e(G) \le \lfloor n^2/4 \rfloor$, completing the induction.

For the extremal case, the complete bipartite graph with parts of size $\lfloor n/2 \rfloor$ and $\lceil n/2 \rceil$ has no triangle (any triangle would need an edge inside one part, but there are none) and has exactly $\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil = \lfloor n^2/4 \rfloor$ edges, so the bound is tight.

Both sides count the same thing — the number of ways to pick $n$ people out of $2n$ — so no algebraic manipulation of binomial coefficients is needed at all, only a careful description of one selection process in two different orders.

Consider a set of $2n$ people consisting of $n$ boys and $n$ girls. We count, in two ways, the number of ways to choose a committee of exactly $n$ people from this set of $2n$.

Directly, by definition, this number is $\binom{2n}{n}$, since we are simply choosing $n$ objects out of $2n$.

Alternatively, split every valid committee according to how many boys it contains. If the committee contains exactly $k$ boys for some $k$ with $0 \le k \le n$, then those $k$ boys can be chosen in $\binom{n}{k}$ ways, and the remaining $n-k$ committee members must be girls, chosen from the $n$ girls in $\binom{n}{n-k}$ ways. By the symmetry identity $\binom{n}{n-k} = \binom{n}{k}$, the number of committees with exactly $k$ boys is $\binom{n}{k} \cdot \binom{n}{k} = \binom{n}{k}^2$.

Every valid committee of $n$ people has some well-defined number of boys $k$ between $0$ and $n$, and no committee is counted twice across different values of $k$, so summing over all $k$ gives the total number of committees as $\sum_{k=0}^{n} \binom{n}{k}^2$.

Since both expressions count exactly the same set of committees, they must be equal: $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$.