Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
related: math.stackexchange.com/questions/128657/… –  Paul Aug 31 '13 at 9:41
    
This question is more of an extension of that one. The upper bound for V if G is connected could be less 10 as some regions have a degree higher than 3. –  Yun Fei Ou Yang Aug 31 '13 at 9:44
add comment

1 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:

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:

J. Battle, F. Harary and Y. Kodama, Every planar graph with nine points has a nonplanar complement, Bull. Amer. Math. Soc. 68 (1962), 569-571.

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:

The self-complementary planar graphs on 4 or 5 vertices

And all $8$-vertex self-complementary graphs are connected (whether or not they are planar).

share|improve this answer
    
In fact, all self-complementary graphs are connected. More generally, for any graph $G$, either $G$ or $\overline G$ is connected. This is because, if $G$ is not connected, then $\overline G$ has a complete bipartite graph as a spanning subgraph. –  bof Jan 30 at 0:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.