Can anyone explain me what is a Ramsey Graph with a simple example?
What are its properties?



What is a Ramsey Graph?
The form in which you might be familiar with the result is this:



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


One can then try to determine the smallest such $n$ and this is the respective Ramsey number.


Now, you can rephrase this problem not as a coloring problem but like so:



> 
> For a pairs of parameters $(r,b)$ there exists an $n$ such that for every graph on $n$ vertices there will exist a complete subgraph on $r$ vertices or for the complement of the graph there will exist a complete subgraph on $b$ vertices.
> 
> 
> 


The complement of the graph is precisely the graph with those edges not present in the original graph.
In other words, if you color, consider the graph just formed by the red edges, the complement will be the graph with the blue edges.


Still differently, one says a graph contains a clique of size $r$ if it contains a complete subgraph of that size. Conversely, one says it contains an independent set of size $b$ if there is a set of vertices of size $b$ with no edges among these vertices. (In other words in the complement this will be a clique.)


So, one can also state the result above in the form:



> 
> For every pair of parameters $(r,b)$ there is an $n$ such that each graph on $n$ vertices will contain a clique of size $r$ or an independent set of size $b$.
> 
> 
> 


Now, this result in particular implies that, given $(r,b)$ there are only a finite number of graphs that do *not* have a clique of size $r$ or an independent set of size $b$. Such a graph is then called a **Ramsey graph** for the respective parameters, and sometimes the number of vertices of the graph is given as an additional parameter.


So, a Ramsey graph (with certain parameters) is an example of a graph where what is implied by the respective Ramsey theorem (for sufficiently large graphs) does *not* hold true.
(Of course its number of vertices thus is smaller than the relevant Ramsey number.
And, the maximal number of vertices of a Ramsey graph is just one smaller than the respective Ramsey number.)


