Ramsey’s Theorem: A graph with N vertices has either a clique or an anti-clique with at least 1/2log2N. 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 log2N 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/2log2N elements. C is the set of vertices of a clique and AC is the set of vertices of an anti-clique.