# Ramsey number problem

Let $$K_{n}$$ is the complete graph on $$n$$ vertices and $$T_{m}$$ is a tree on $$m$$ vertices

How do I show that $$R(K_{n} , T_{m}) = (n-1)(m-1) + 1$$?

Here $$R(G,H)$$ is the minimum $$t \in \mathbb{N}$$ such that every $$2$$ coloring of edges of $$K_{t}$$ yields a red $$G$$ or a blue $$H$$, for graphs $$G,H$$. I was thinking of using induction but I am stuck.

• Are you certain it's an equality? If yes, can you find a graph of $(n-1)(m-1)$ vertices that doesn't contain a $K_n, T_m$? – Calvin Lin Apr 11 '20 at 15:47
• Yes, I believe you have to find a 2 coloring of $K_{(n-1)(m-1)}$ such that it has no red $K_{n}$ or blue $T_{m}$. – user100101212 Apr 11 '20 at 15:54
• Can you add that construction into the question? It can help motivate what "structure avoider" we need. – Calvin Lin Apr 11 '20 at 15:55
• Induction on $m$ works. What have you tried? If you show your work, I'd undelete my solution. – Calvin Lin Apr 11 '20 at 16:04
• @Calvin, why would the single edge be connected to the $T_m$? – Empy2 Apr 11 '20 at 16:11

The original source of this result seems to be a one-page note of Václav Chvátal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977), 93. I haven't seen Chvátal's note, but I suppose his argument is something like the following.

The inequality $$R(K_n,T_m)\ge(n-1)(m-1)+1$$ is trivial; there is an obvious red/blue coloring of the edges of a complete graph of order $$(n-1)(m-1)$$ with no red $$K_n$$ and no blue tree of order $$m$$.

I have to show that $$R(K_n,T_m)\le(n-1)(m-1)+1.$$ Let me restate it this way:

Theorem. If $$G$$ is a graph of order $$r=(n-1)(m-1)+1$$ with independence number $$\alpha(G)\lt n$$, then $$G$$ contains an isomorphic copy of every tree of order $$m$$.

We can assume that $$n\gt1$$. Since $$\chi(G)\ge\frac r{\alpha(G)}\ge\frac r{n-1}\gt m-1,$$ we have $$\chi(G)\ge m$$, and so $$G$$ contains a minimal $$m$$-chromatic subgraph $$H$$, which has minimum degree $$\delta(H)\ge m-1$$. Thus it will suffice to prove the following:

Lemma. If $$H$$ is a graph with minimum degree $$\delta(H)\ge m-1$$, then $$H$$ contains an isomorphic copy of every tree of order $$m$$.

The lemma is easily proved by induction on $$m$$. Maybe it's a theorem or exercise in your graph theory textbook; e.g., it's Proposition 2.1.8 on p. 70 of Douglas B. West's Introduction to Graph Theory, Second Edition.