Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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.

Perhaps what he means is to emphasize that the elements of the first partition are pairwise disconnected from the elements of the second partition (as well as from one another).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.