 According to Ramsey 's theorem , every n @-@ vertex undirected graph has either a clique or an independent set of size logarithmic in n . The precise size that can be guaranteed is not known , but the best bounds known on its size involve binary logarithms . In particular , all graphs have a clique or independent set of size at least 1 / 2 log2 n ( 1 − o ( 1 ) ) and almost all graphs do not have a clique or independent set of size larger than 2 log2 n ( 1 + o ( 1 ) ) . 
