Complement of a bipartite graph
Task number: 3596
Does there exist a bipartite graph with at least \(5\) vertices whose complement is also bipartite?
Solution
No: one of its parts contains at least three vertices and in the complement these three vertices will form a triangle.
A graph containing a triangle cannot be bipartite, because two of these vertices would have to be in the same part.
Answer
There is no such graph.
