6 Ramsey Theory
\(G\) is an \((x,y)\)-graph if \(x {\gt} C(G)\) and \(y {\gt} I(G)\).
\[ R(x,y) = \max \{ n \in \mathbb {N} \mid \exists G \text{, } G \text{ is an} (x, y)\text{-graph } \land \text{ } |V(G)| = n \} \]
\(G\) is an \((x,y)\)-graph if and only if its complement \(G^c\) is a \((y,x)\)-graph.
Proof
Proof
Proof
Proof
Proof
Proof
Proof
Proof
Proof
Proof
Proof
For any \((x,y,n)\)-graph \(G\), every vertex \(v\) in \(G\) satisfies
\[ (n - 1) - R(x,y - 1) \leq deg(v) \leq R(x - 1, y) \]
.
Proof
Proof
Proof
Proof
Proof
Proof
Proof
Proof
Proof
Proof
Proof