Ramsey’s theorem$:$ Let $G$ be a graph. A clique in $G$ is a sub-graph in which every two nodes are connected by an edge. An anti-clique also called an independent set, is a sub-graph in which every two nodes are not connected by an edge. Show that every graph with $n$ nodes contains either a clique or an anti-clique with at least $\frac{1}{2}log_{2}n$ nodes.
