0
$\begingroup$

For context, I am in an intro Graph theory course. I know that the complement of a bipartite graph can be bipartite, but I don't know how to determine all of them and whether they can be complete. I assume the intersection is not empty but I am not sure. Any help is appreciated, thanks!

$\endgroup$
0
$\begingroup$

The complement of a complete bipartite graph $K_{m,n}$ is the union of the two complete graphs $K_m\cup K_n$. That complement is bipartite if and only if $m<3$ and $n<3$. If $m,n>0$ then the complement will never be complete since it is not even connected.

$\endgroup$
2
  • $\begingroup$ Thank you so much! Why m,n<3 though? $\endgroup$ – Mia Jan 26 '20 at 22:32
  • $\begingroup$ @Maria because anything larger than that would have an odd cycle, like a cycle of length 3, that keeps a graph from being bipartite. $\endgroup$ – user694818 Jan 26 '20 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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