Let G=(V,E) be a simple and self complementary graph. What is the maximum number of vertices it can have if both it and its complement are planar when i) G is connected?
ii)G is not necessarily connected?
I attempted part i) could be solved using a corollary of Euler's theorem, that e is smaller than or equal to 3v-6. Rewriting e as v(v-1)/2 and rearranging yields v(13-v) is greater than or equal to 24, meaning that v can take a maximum value of 10.
*The flaw in this proof is that not all regions have degree 3 and the actual maximum value for V can be less than 10. Are there any ways to prove this definitively?
Is the upper limit for V finite for the second, more general case? What tricks and theorems are useful for solving these questions?
Best Answer
Good so far. If $G$ has $e$ edges, then $\overline{G}$ has $\binom{v}{2}-e$ edges. And since $G$ and $\overline{G}$ are both planar $e \leq 3v-6$ and $\binom{v}{2}-e \leq 3v-6$ which combine to imply $v \leq 10$. This leaves $v \in \{0,1,\ldots,10\}$.
Since $G$ is self-complementary, it has the same number of edges as $\overline{G}$. Hence $e=\binom{v}{2}-e$, and $\binom{v}{2}$ must be even. This leaves $\{0,1,4,5,8,9\}$.
Easy examples exist for $v \in \{0,1,4,5\}$ (a $4$-vertex path and a $5$-cycle in the non-trivial cases). The following is a self-complementary $8$-vertex planar graph:
The graph is drawn along with its complement, and an isomorphism between the two is indicated by the colours. (Source: University of California, Santa Cruz notes: pdf.)
There are $36$ non-isomorphic $9$-vertex self-complementary graphs (according to http://oeis.org/A000171). They are included in McKay's data: http://cs.anu.edu.au/~bdm/data/graphs.html One could exclude the possibility of a $9$-vertex self-complementary graph by finding a $K_{3,3}$ or $K_5$ subdivison (or $K_{3,3}$ or $K_5$ minor) in each of these graphs $36$ graphs.
This is too much legwork for me, so I'll instead refer to this paper:
A direct corollary is that there are no $9$-vertex self-complementary planar graphs. We conclude that the maximum number of vertices in a self-complementary planar graph is $8$.
We also find that there are no disconnected self-complementary planar graphs. We can prove this by inspection of McKay's data. The self-complementary (planar) graphs on $4$ or $5$ vertices are drawn below:
And all $8$-vertex self-complementary graphs are connected (whether or not they are planar).