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.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email