km

Show that in any group of six people, there are either 3 mutual strangers or 3 mutual acquaintances. A clique in a graph is a complete subgraph (i.e., all nodes are connected with edges). Show that every graph with N nodes contains a clique or the complement of a clique, of size at least 1/2 log_2 N