# Ramsey Number.

• MathematicalPhysicist
In summary, the conversation discusses the relationship between Ramsey numbers and vertex coloring in graph theory. It is stated that every red-blue coloring of the edges in a graph G will contain either a red copy of K_s or a blue copy of K_t. The goal is to prove that R(s,t) is less than or equal to the vertex coloring minimum number of G, denoted as \chi(G). The speaker suggests using a graph L(G) to represent the edges of G and prove the inequality (1) \binom{s+t-2}{t-1}\le\chi(G)=\chi'(L(G)). They also mention that this result can be achieved using Szkres-Erdos. The conversation ends with a solution

#### MathematicalPhysicist

Gold Member
I have this next question which I am trying to resolve.
Let G=(V,E) be some graph (usually in this context threre aren't loops nor directed edges),assume that every red-blue colouring of the edges of G contains a red copy of $$K_s$$ or blue copy of $$K_t$$. show that $$R(s,t)\le\chi(G)$$, where R(s,t) is ramsey number and $$\chi(G)$$ is vertex colouring minimum number of G.

Now I thought of proving that $$(1)\binom{s+t-2}{t-1}\le\chi(G)=\chi'(L(G))$$
where L(G) is the graph in which you identify each edge of G as a vertex and each vertex in G which is common with two edges in G as an edge in L(G); $$\chi'(L(G))$$ is the edges colouring index of L(G).
How do I show (1), I am not sure?

I forgot to say that if I prove (1), then by Szkres-Erdos I am done.

Consider a vertex colouring of G with n=Chi(G) colours and take any red-blue edge colouring of K_n. If an edge in G has end-vertices coloured i and j, colour it the same as the edge ij in K_n. G must contain either blue K_s or red K_t with distinctly coloured vertices and hence K_n must contain either a blue K_s or red K_t, so Chi(G)>=R(s,t).

Thanks.

Easy than I thought it would be.