What is a Ramsey Graph? What is a ramsey graph and What is its relation to RamseyTheorem?
In Ramsey Theorem:
for a pairs of parameters (r,b) there exists an n such that for every (edge-)coloring of the complete graph on n vertices with colors r(ed) and b(lue) there will exist a complete subgraph on r vertices colored red or a complete subgraph on b vertices colored blue.
Ramsey Graph :
A Ramsey graph is a graph with n vertices, no clique of size s, and no independent set of size t.
I couldnt understand how the above two are related.
Can any one explain what is a Ramsey Graph as simple as possible? (in terms of coloring)
 A: Instead of considering a complete graph $K_n$ whose edges are red and blue, just consider some graph $G$ with $n$ vertices.  Let $\bar G$ be the complement of $G$.  $\bar G$ contains a clique of size $s$ if and only if $G$ contains an independent set of size $s$.
Now consider  $G$ as a subgraph of $K_n$.  Color the edges of $G$ in  $K_n$ red, and color the other edges of the $K_n$, that is the edges of $\bar G$, blue.
Now $K_n$ contains a red $K_r$ if and only if $G$ contains a clique of size $r$, and $K_n$ contains a blue $K_b$ if $\bar G$ contains a clique of size $b$, which is true if and only if $G$ contains an independent set of size $b$.
The Ramsey theorem says that for given $r$ and $b$ there is an $n$ such that (what you said about $K_n$).  A Ramsey graph of size $q$ is a counterexample  to the Ramsey theorem, and when it exists, it shows that $n$, which must exist, must be larger than $q$.
Here is an example.  Let's take $r=b=3$.  The Ramsey theorem says that there is some $n$ such that if we color edges of $K_n$ in red and blue, there is either a red triangle or a blue triangle.
There are many Ramsey graphs.  For example, consider $K_2$.  It has neither a clique of size $r=3$ nor an independent set of size $b=3$ and therefore it is a ramsey graph for $r=3, b=3$ and shows that the $n$ of the previous paragraph  must be bigger than 2.
Now consider $C_5$, the cycle on five vertices.  It has neither a clique of size $r=3$ nor an independent set of size $b=3$ and therefore it is a ramsey graph for $r=3, b=3$ and shows that the $n$ given  by the Ramsey theorem must be bigger than 5.
The Ramsey theorem claims that when $n$ is large enough, there is no Ramsey graph with $n$ or more vertices.
A: Given natural numbers $r,b$ Ramsey's Theorem states that there is a natural number $n$ such that if you colour the edges of $K_n$, the complete graph on $n$ vertices, you get either a copy of $K_r$ all edges of which are coloured red, or a copy of $K_b$ all edges of which are coloured blue.  Let us denote by $R(r,b)$ the least such number $n$, this is called the Ramsey number of $r$ and $b$.
A Ramsey graph (with respect to integers $s$ and $t$) is just some some graph containing neither a copy of $K_s$ nor a copy of the "trivial graph" on $t$ vertices (a graph where there are no edges).  Note that if $( G , E )$ is a Ramsey graph with respect to $s,t$ on $n$ vertices, we can create a colouring of $K_n$ as follows:


*

*Enumerate $G = \{ v_1 , \ldots , v_n \}$.

*If there is an edge between $v_i$ and $v_j$ in $G$, colour the edge $\{ i , j \}$ in $K_n$ red; otherwise colour that edge blue.


It should be easy to see that in $K_n$ there is no copy of $K_s$ all edges of which are coloured red: if there was we could translate this to a clique of size $s$ in the original graph $(G,E)$.  And neither is there a copy of $K_t$ all edges of which are coloured blue.  Therefore this colouring serves as proof that $R ( s,t ) > n$.  Or, equivalently, the existence of a Ramsey graph for $s,t$ on $n$ vertices serves as proof that $R(s,t) > n$.
