Cheap and Secure Web Hosting Provider : See Now

[Answers] Can I find a clique with more than 2 nodes in a bipartite graph?

, , No Comments
Problem Detail: 

As in the title, is it possible to find a clique with more than 2 nodes in a bipartite graph?

Asked By : Frank

Answered By : Juho

A graph is bipartite if and only if it is 2-colorable. A clique of size at least 3 contains a triangle, and a triangle $K_3$ clearly cannot be colored with 2 colors. It follows we can't find a triangle in a bipartite graph, so the corresponding decision problem is very easy for a bipartite graph.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42302

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback