**Ramsey’s Theorem**: A graph with N vertices has either a clique or an
anti-clique with at least 1/2log_{2}N. Clique is a subgraph of
a graph where each pair of vertices is connected. Anti-clique is a
subgraph where each pair of vertices is not connected.

* *

*Proof:* Initialize
two empty sets C and AC. For every node n in graph, if the degree of n
is greater than half of the no. of remaining nodes, put n to C
otherwise to AC. Then delete all nodes that are not connected
(connected) to n if n adds to C (AC). Then each time at most half of
the remaining nodes are deleted, so there are log_{2}N steps
until all nodes are put into one set. For each step, a node is added
either to C or AC. Hence, one of the set has at least 1/2log_{2}N
elements. C is the set of vertices of a clique and AC is the set of
vertices of an anti-clique.