# How does an independent set induce a biclique in a bipartite graphs?

Fixee wrote

Every independent set induces a clique in the complement graph (or a biclique in the case of bipartite graphs).

I wonder how an independent set induces a biclique in a bipartite graphs?

Thanks!

-

This probably refers to its bipartite complement. If you have a bipartite graph with the vertex bipartition $U \cup V$, then the edges in its complement are $$\{uv: u \in U, v \in V \text{ and } uv \text{ not an edge in } G\}.$$

There's a similar ambiguity in the use of the term adjacency matrix for bipartite graphs; some people call the bi-adjacency matrix simply the adjacency matrix.

-
Thanks! So do a maximum independent set in a bipartite graph and a maximum biclique in its bipartite complement induce each other? –  Tim Nov 3 '12 at 23:28
An independent set is a pairwise non-adjacent set of vertices. Thus in the complement, every vertex will be incident to every other vertex, whence the set forms a clique. The only biclique which is also a clique is $K_2$. I think Fixee may have misspoken.