Minimum number of edges in graph with Ramsey property

Question

I have the following problem, but I can't seem to crack it:

Let $G = (V, E)$ be a graph with the property that any 2-coloring of its edges will contain a monochromatic copy of $K_{t}$. Show that $|E| \geq {R(t) \choose 2},$ for $R(t)$ the $t$th Ramsey number.

So far, my approach has been to use a proof by contradiction, but I'm not having much luck arriving at a useful contradiction. How does one prove this?

Edit: The paper https://users.renyi.hu/~p_erdos/1978-48.pdf linked below by user14111 contains a stronger rendition of this proof for general $R(K_{t}, K_{s}).$

Answer 1

This my presentation of the proof in given in the source below:

Erdős, P., Faudree, R.J., Rousseau, C.C. et al. The size Ramsey number. Period Math Hung 9, 145–161 (1978). https://doi.org/10.1007/BF02018930

I will show the contrapositive, that every graph with at most $\binom{R(t,t)}2-1$ edges has a $2$-coloring with no monochromatic $K_t$'s. I will prove this by induction on $|V|$.

If $|V|<R(t,t)$, then the claim is trivial, by definition of $R(t,t)$. This proves the base case. Assume $|V|\ge R(t,t)$, and assume by induction that the claim holds for all graphs with a smaller vertex set than that of $G$. In order to have $|E|<\binom{R(t,t)}2$, there must exist a pair of non-adjacent vertices, call them $u$ and $v$.

Define the equivalence relation $\equiv$ on $V$ where $u\equiv v$ is the only nontrivial equivalence. Let $G'=(V',E')$ be the quotient graph with respect to $\equiv$. Since $G'$ has one fewer vertex than $G$, we may apply the inductive hypothesis to get a $2$-coloring of $G'$ with no monochromatic $K_t$'s. We then use this to get a $2$-coloring of $G$. We have a coloring of the edges $G',$, which is a map $c:E' \to \{\text{red},\text{blue}\}.$ There is also the quotient map $\pi:G\to G'$, which induces a map $\pi:E\to E'$ via $\pi(\{x,y\})=\{\pi(x),\pi(y)\}$. This is well-defined for this particular quotient map because whenever $x$ and $y$ are adjacent in $G$, they are in distinct equivalence classes. The coloring for $G$ is $c\circ \pi$.

To see there are no monochromatic $K_t$'s in this coloring of $G$, let $K$ be an arbitrary subgraph of $G$ isomorphic to $K_t$. This $K$ must exclude at least one of $u$ and $v$, since $u$ is not adjacent to $v$. This means the vertices in $K$ are in distinct equivalence classes with respect to $\equiv$, which implies that $\pi (K)$ is a $K_t$ in $G'$ with the same coloring as that of $K$. Since our coloring of $G'$ had no monochromatic $K_t$'s, this implies the same is true for $G$.