= Solution
Let $G$ have $n$ vertices and $e$ edges. Its <complement graph> $\overline G$ has
$$
\binom n2-e
$$
edges. If both graphs were <planar graph>[planar], the <planar graph edge bound> would give
$$
\binom n2=e+e(\overline G)
\le(3n-6)+(3n-6)=6n-12.
$$
Equivalently, $n^2-13n+24\le0$, whose larger root is $(13+\sqrt{73})/2<11$. Thus an integer $n\ge11$ is impossible, proving that
$$
\boxed{\text{no planar graph of order greater than 10 has a planar complement}}.
$$
Now suppose that $G$ and $\overline G$ are both <bipartite graph>[bipartite]. In a bipartition $V(G)=A\sqcup B$, every pair within $A$ and every pair within $B$ is adjacent in $\overline G$. Since a bipartite graph contains no triangle, $|A|,|B|\le2$, and hence $|V(G)|\le4$. Equality is attained by the path $P_4$, whose complement is again a copy of $P_4$. Therefore the maximum order is
$$
\boxed4.
$$
Back to article page
