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.

  • $\begingroup$ 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$? $\endgroup$ – Calvin Lin Apr 11 '20 at 15:47
  • $\begingroup$ 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}$. $\endgroup$ – user100101212 Apr 11 '20 at 15:54
  • $\begingroup$ Can you add that construction into the question? It can help motivate what "structure avoider" we need. $\endgroup$ – Calvin Lin Apr 11 '20 at 15:55
  • $\begingroup$ Induction on $m$ works. What have you tried? If you show your work, I'd undelete my solution. $\endgroup$ – Calvin Lin Apr 11 '20 at 16:04
  • $\begingroup$ @Calvin, why would the single edge be connected to the $T_m$? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.