Extremal Graph Theory and Ramsey Theory

Induct on $n$. For $n \le 2$ there are at most $\lfloor n^2/4\rfloor$ possible edges at all (0 for $n\le1$, $1$ for $n=2$), so the bound holds trivially. For $n \ge 3$, let $G$ be triangle-free on $n$ vertices. If $G$ has no edges, $|E|=0 \le \lfloor n^2/4\rfloor$ and we are done; otherwise pick an edge $uv$. Since $G$ is triangle-free, $u$ and $v$ have no common neighbor (a vertex adjacent to both would close a triangle with $uv$), so $N(u) \cap N(v) = \emptyset$ and $N(u) \cup N(v) \subseteq V$ gives $\deg(u) + \deg(v) = |N(u) \cup N(v)| \le n$. $u$ and $v$ leaves a triangle-free graph on $n-2$ vertices, with at most $\lfloor(n-2)^2/4\rfloor$ edges by the inductive hypothesis. Every edge of $G$ either lies in this smaller graph, or touches $u$ or $v$; the edges touching $u$ or $v$ number $\deg(u)+\deg(v)-1$ (the $-1$ corrects for $uv$ itself, counted in both degrees). So

Since $|E(G)|$ is an integer, $|E(G)| \le \lfloor n^2/4\rfloor$, completing the induction. Equality forces $\deg(u)+\deg(v)=n$ and the smaller graph to be extremal at every step, which pins the graph down to the balanced complete bipartite graph.

Let $G$ be a $K_{r+1}$-free graph on $n$ vertices with the MAXIMUM possible number of edges (an extremal graph); such a $G$ exists since there are finitely many graphs on $n$ vertices.

Step 1 (symmetrization). Suppose $u,v$ are non-adjacent in $G$ with $\deg(v) \ge \deg(u)$. Form $G\prime$ by deleting all of $u$s edges and joining $u$ instead to exactly $N(v)$ (making $u$ a "twin" of $v$). This changes the edge count by $\deg(v)-\deg(u) \ge 0$, so $G\prime$ has at least as many edges as $G$. $G\prime$ stays $K_{r+1}$-free: $u,v$ are still non-adjacent in $G\prime$ (and so cannot both lie in one clique), so any clique of $G\prime$ uses at most one of them. A clique avoiding $u$ entirely uses only original edges of $G$ restricted to $V \setminus \{u\}$, so it was already a clique of $G$. A clique using $u$ (not $v$) uses only edges from $u$ to $N(v)$; replacing $u$ by $v$ in that clique uses only edges from $v$ to $N(v)$, all present in $G$ already, so it corresponds to an equal-size clique of $G$. Either way, a $K_{r+1}$ in $G\prime$ would force one in $G$, contradicting $G$s $K_{r+1}$-freeness. So $G\prime$ is $K_{r+1}$-free with at least as many edges as $G$; since $G$ was already extremal, $G\prime$ has EXACTLY as many edges, which forces $\deg(u)=\deg(v)$, and $G\prime$ (now also extremal) may replace $G$.

Step 2 (complete multipartite structure). Repeating Step 1 across every non-adjacent pair, we may assume $G$ itself satisfies: $N(u)=N(v)$ for every non-adjacent pair $u,v$. Define $u \sim v$ when $u=v$ or $u,v$ are non-adjacent. This is an equivalence relation: reflexive and symmetric are immediate, and if $u\sim v\sim w$ with $u\ne w$ then $N(u)=N(v)=N(w)$, and $w \notin N(v)=N(u)$, so $u,w$ are non-adjacent too, giving $u\sim w$. The equivalence classes $V_1,\ldots,V_k$ are each independent sets by definition, and any two vertices in DIFFERENT classes are adjacent (else they would be $\sim$-related into the same class). So $G$ is complete $k$-partite. Since $K_{r+1}$-free, $k \le r$ (choosing one vertex from each of $r+1$ distinct parts, if $k\ge r+1$, would give a $K_{r+1}$, as all cross-pairs are edges).

Step 3 (balance the parts). Among complete multipartite graphs on $n$ vertices with at most $r$ parts, the edge count is $\binom n2 - \sum_i\binom{n_i}2$, maximized by minimizing $\sum_i \binom{n_i}2$. Using exactly $r$ parts beats fewer (splitting one part into two never-connected pieces only removes the $\binom{n_i}2$ term for edges that did not exist, while every other part still gains a partner, so it strictly helps once $k<r$, unless some $n_i=0$, treated as using fewer parts than allowed). If two parts have sizes differing by $\ge 2$, say $n_i \ge n_j+2$, moving one vertex from part $i$ to part $j$ changes $\binom{n_i}2+\binom{n_j}2$ by $-(n_i-1)+n_j = n_j-n_i+1 \le -1 < 0$, strictly decreasing the sum and so strictly increasing the edge count — contradicting extremality unless the parts are already balanced, differing by at most $1$. So the extremal complete multipartite graph has exactly $r$ parts, sizes $\lceil n/r\rceil$ or $\lfloor n/r\rfloor$: this is exactly $T(n,r)$, and $e(G) = e(T(n,r))$.

Two halves. $R(3,3) > 5$: the pentagon/pentagram coloring of $K_5$ (Ramsey Numbers and $R(3,3)=6$) has no monochromatic triangle, so some $2$-coloring of $K_5$ avoids one, meaning $5$ is not large enough to force one. $R(3,3) \le 6$: let $v$ be any vertex of any $2$-colored $K_6$. It has $5$ edges to the other vertices; since $5 = 2\cdot2+1$, by pigeonhole at least $\lceil 5/2\rceil = 3$ of them share a color, say red, going to vertices $a,b,c$. If some edge among $a,b,c$ is red, it closes a red triangle with $v$. If none is, all three of $ab,ac,bc$ are blue, and $a,b,c$ is itself a blue triangle. Either way $K_6$ has a monochromatic triangle, and $v$ and the coloring were arbitrary, so EVERY $2$-coloring of $K_6$ has one. Combining the two halves: $5 < R(3,3) \le 6$, so $R(3,3)=6$.

Let $n = R(s-1,t)+R(s,t-1)$ and take any $2$-coloring of $K_n$. Fix a vertex $v$; it has $n-1 = R(s-1,t)+R(s,t-1)-1$ other vertices, split by color into its red neighbors $A$ and blue neighbors $B$, $|A|+|B|=n-1$. If $|A| < R(s-1,t)$ and $|B| < R(s,t-1)$ then $|A|+|B| \le (R(s-1,t)-1)+(R(s,t-1)-1) = n-2 < n-1$, a contradiction; so $|A|\ge R(s-1,t)$ or $|B|\ge R(s,t-1)$. $|A|\ge R(s-1,t)$. By definition of the Ramsey number, the coloring restricted to $A$ contains a red $K_{s-1}$ or a blue $K_t$. A blue $K_t$ inside $A$ is already a blue $K_t$ in the whole graph. A red $K_{s-1}$ inside $A$, together with $v$ (which is joined RED to every vertex of $A$), forms a red $K_s$. Either way the coloring of $K_n$ has a red $K_s$ or a blue $K_t$. The case $|B|\ge R(s,t-1)$ is symmetric, swapping colors. So every $2$-coloring of $K_n$ has the desired clique, giving $R(s,t) \le n = R(s-1,t)+R(s,t-1)$. the binomial corollary, induct on $s+t$. The base cases match the claimed formula: $R(s,2)=s=\binom{s+2-2}{s-1}=\binom{s}{s-1}$ and $R(2,t)=t=\binom{2+t-2}{2-1}=\binom{t}{1}$. For the inductive step, assuming $R(s-1,t)\le\binom{s+t-3}{s-2}$ and $R(s,t-1)\le\binom{s+t-3}{s-1}$, the recursion just proved gives

by Pascals identity, completing the induction.

First the general principle used throughout the Probabilistic Method: if $X$ is a random variable taking non-negative integer values and $\mathbb E[X] < 1$, then $\Pr[X=0] > 0$ — otherwise $X \ge 1$ always, forcing $\mathbb E[X]\ge1$. Applied here, $X$ counts monochromatic $k$-sets in a uniformly random $2$-coloring of $K_n$; linearity of expectation over the $\binom nk$ possible $k$-sets, each monochromatic with probability $2^{1-\binom k2}$ (independently of the others coloring, though linearity needs no independence between terms), gives $\mathbb E[X]=\binom nk 2^{1-\binom k2}$ exactly as stated in the Probabilistic Method section. fix $k \ge 3$ and let $n=\lfloor 2^{k/2}\rfloor \le 2^{k/2}$. Since $\binom nk = \frac{n(n-1)\cdots(n-k+1)}{k!} \le \frac{n^k}{k!}$,

It remains to show $k! > 2^{1+k/2}$ for every $k\ge3$, by induction. Base case $k=3$: $3!=6$ and $2^{1+1.5}=2^{2.5}\approx5.66 < 6$. Inductive step: if $k!>2^{1+k/2}$ for some $k\ge3$, then $(k+1)! = (k+1)\cdot k! > (k+1)\cdot2^{1+k/2}$, and since $k+1\ge4>\sqrt2$, this exceeds $\sqrt2\cdot2^{1+k/2} = 2^{1+(k+1)/2}$, completing the induction. $\mathbb E[X] \le 2^{1+k/2}/k! < 1$ for every $k\ge3$, meaning some $2$-coloring of $K_n$ (for $n=\lfloor2^{k/2}\rfloor$) has zero monochromatic $k$-sets, so $R(k,k) > n \ge 2^{k/2}-1$, i.e. $R(k,k) > \lfloor2^{k/2}\rfloor$. This is Erdőss classical $1947$ theorem, the paper usually credited with founding the probabilistic method.