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!
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.
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).