9
$\begingroup$

Show that there exists a self-complementry graph of order $ n $ if and only if $ n = 0$ or $ 1 \ (\mbox{mod } 4) $.

My thoughts so far:

I've proven the 'only if' direction.

For the 'if' direction, I need to show that if $ n = 0$ or $ 1 \ (\mbox{mod } 4) $ then I can construct a self-complementary graph. I've started by focusing on the case $ n = 0 \ (\mbox{mod } 4) $; in particular, I've drawn such a graph in the case n = 4 (a Z shape). But I'm struggling to generalise my method to n = 8 and higher (in fact, I haven't successfully constructed a self-complementary graph of order 8). I'm not really sure how to think about this; I'm new to Graph Theory and so haven't had much practice yet. EDIT: I've had a further thought. The graph I construct must have exactly $ \frac{n(n-1)}{4} $ edges.

I'd prefer hints to full answers, at least until I can reach the answer myself. Thanks for your help!

  • 0
    See [this answer](http://math.stackexchange.com/questions/40745/constructing-self-complementary-graphs/412930#412930)2015-12-31

3 Answers 3

1

Hint:

Given a self complementary graph on $n$ vertices, try to construct a self-complementary graph on $n+4$ vertices.

Elaboration on the hint:

Given a self-complementary graph $G$ with $n$ vertices, add 4 more vertices which already form a 'Z' graph (the self-complementary graph for $n=4$). Connect the vertices of $G$ to some of four newly added vertices. Show that the new graph so formed, is a self-complementary graph on $n+4$ vertices.

Full answer:

Connect every vertex of $G$ to two of the vertices which are the farthest apart on the the n=4 graph (which is basically a path, and you connect all vertices of $G$ to the end points of that path).

This works even when $G$ has only one vertex.

  • 0
    @SalmonKiller: I have added more explanation...2015-11-25
0

Almost a spoiler hint:

When I had to prove this, I created solutions for cases n=4 and n=5 and generalized the individual solutions from those to sets of 4 (members of sets must form a complete graph between themselves) with extra node "in middle" for case where n=1(mod 4).

Since you've already created a solution for n=4, you are more than halfway there.

My professors proof only used two sets (and middle node for n=1(mod 4)), however my proof was deemed perfectly acceptable.

0

Recursive constructions are very popular. The construction given in this answer (which I posted in a previous life) seems to be much less popular, but it is also quite simple. To wit:

Take a complete graph with vertex set $V$ and edge set $E={V\choose2}$. Let $\alpha$ be any permutation of $V$ in which the length of each cycle is a multiple of $4$, except for at most one $1$-cycle. (Of course, such permutations exist if and only if $|V|\equiv 0$ or $1\pmod 4$.)

Let $\beta$ be the permutation of $E$ induced by $\alpha$. Observe that $\beta$ contains only cycles of even length. Color the edges in each cycle alternately black and white. The graph $G$ consisting of the black edges is self-complementary. (The permutation $\alpha$ is an anti-automorphism of $G.$)

Example. To construct self-complementary graphs of order $5$, take $V=\{a,b,c,d,e\}$ and let $\alpha=(a\;b\;c\;d)(e)$ so that $\beta=(ab\;bc\;cd\;ad)(ac\;bd)(ae\;be\;\;ce\;de)\;$. If we choose the edges $ab,cd$ and $ac$ (i.e. "color them black") we get a $4$-point path $P_4$. Now we can choose the edges $be,de$ obtaining the self-complementary graph $C_5$, or else we can choose $ae,ce$ obtaining the other self-complementary graph of order $5$, the one that looks like the letter A.

This construction is completely general, in that every self-complementary graph can be obtained as an instance of this construction.