Proving Ramsey Number Theorem: R(s,t) ≤ χ(G) for Graph G

[MathematicalPhysicist]

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?

 

[MathematicalPhysicist]

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

 

[bpet]

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).

 

[MathematicalPhysicist]

Thanks.

Easy than I thought it would be.

 

[blue_raver22]

I can provide some guidance on how to approach this problem. First, let's define some terms to make sure we are on the same page:

- Ramsey Number Theorem: This is a theorem in graph theory that states that for any two positive integers s and t, there exists a minimum number R(s,t) such that any complete graph with R(s,t) or more vertices will have either a red clique of size s or a blue clique of size t.
- Graph G: This is a graph with a set of vertices V and a set of edges E.
- Vertex Colouring: This is a coloring of the vertices of a graph such that no two adjacent vertices have the same color.
- χ(G): This is the minimum number of colors needed to color the vertices of G such that no two adjacent vertices have the same color.
- L(G): This is a graph obtained by identifying each edge of G as a vertex and each vertex in G that is common to two edges as an edge in L(G).
- χ'(L(G)): This is the minimum number of colors needed to color the edges of L(G) such that no two adjacent edges have the same color.

Now, to prove that R(s,t) ≤ χ(G), we need to show that any red-blue coloring of the edges of G contains either a red clique of size s or a blue clique of size t. This can be done by showing that any red-blue coloring of the edges of L(G) contains either a red clique of size s or a blue clique of size t.

To do this, we can use the fact that χ'(L(G)) = χ(G). This means that any coloring of the edges of L(G) can be translated into a coloring of the vertices of G, and vice versa. So, if we can show that any coloring of the vertices of G contains either a red clique of size s or a blue clique of size t, then we have also shown that any coloring of the edges of L(G) contains either a red clique of size s or a blue clique of size t.

To show this, we can use the pigeonhole principle. Assume that the minimum number of colors needed to color the vertices of G without any adjacent vertices having the same color is χ(G). This means that there are χ(G) different colors available for the vertices of G. Now, consider a complete graph with χ(G