As in the title, is it possible to find a clique with more than 2 nodes in a bipartite graph?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
