  Motivated by its relation to the length of cutting plane proofs for the
Maximum Biclique problem, we consider the following communication game on a
given graph G, known to both players. Let K be the maximal number of vertices
in a complete bipartite subgraph of G, which is not necessarily an induced
subgraph if G is not bipartite. Alice gets a set A of vertices, and Bob gets a
disjoint set B of vertices such that |A|+|B|>K. The goal is to find a nonedge
of G between A and B. We show that O(\log n) bits of communication are enough
for every n-vertex graph.
