The complement of a simple graph has exactly the edges absent from the original graph; a vertex of degree acquires degree .
If a graph and its complement graph are both 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.
