Simultaneously bipartite graph and complement
= Simultaneously bipartite graph and complement
If a graph and its <complement graph> are both <bipartite graph>[bipartite], then the graph has at most four vertices. Indeed, each part of a bipartition of the original graph induces a clique in the complement and therefore has at most two vertices. The bound is attained by the four-vertex path, whose complement is another four-vertex path.