4
$\begingroup$

Counting edges easily shows that if $n$ is congruent to 2 or 3 modulo 4, there is no self-complementary graph on $n$ vertices. Is the converse true?

What I know: Paley graphs are self-complementary, so if $n$ is congruent to 1 mod 4 and is a prime power, then there is a self-complementary graph on $n$ vertices. Also, the set of $n$ such that there is a self-complementary graph on $n$ vertices is closed under products. Together (since there is a self-complementary graph on 4 vertices) these imply that if the prime factorization of $n$ has even number of 2s and an even number of every prime congruent to 3 modulo 4 then there is a self-complementary graph on $n$ vertices.

$\endgroup$
  • $\begingroup$ This follows from formulas (4) and (5) of this paper: doi.org/10.1112/jlms/s1-38.1.99 $\endgroup$ – Ian Agol Aug 31 '18 at 20:10
  • 3
    $\begingroup$ This is a standard exercise in graph theory textbooks. $\endgroup$ – bof Aug 31 '18 at 20:59
7
$\begingroup$

Note that if $G$ be a self-complementary graph with $n$ vertices, then the following gives a self-complementary graph $H$ on $n+4$ vertices: Let $H$ be the graph obtained by adding 4 new vertices $\{a,b,c,d\}$ to $G$, with edges $(a,b),(b,c),(c,d), (a,x), (d, x)$ for any vertex $x$ of $G$.

Why $H$ is self-complementary? As $G$ is self-complementary, there is a permutation $f:V(G)\to V(G)$ such that, for any $u,v$ distinct vertices of $G$, $(u,v)$ is an edge in $G$ if and only if $(f(u),f(v))$ is not an edge in $G$. We can define $g:V(H) \to V(H)$ by $g(a)=b; g(b)=d; g(c)=a; g(d)=c$ and $\left. g\right|_{V(G)} = f$, and it is easy to see that $g$ is an isomorphism between $H$ and its complement.

As there are self-complementary graphs on $1$ vertex and on $4$ vertices, it follows that, for any $n=0,1\quad (mod 4)$ there is a self-complementary graph on $n$ vertices.

$\endgroup$
  • $\begingroup$ Nice construction. It works for 0 points, but not for 1 point. Perhaps cx and not bx? Gerhard "Hasn't Checked On Larger Graphs" Paseman, 2018.08.31. $\endgroup$ – Gerhard Paseman Aug 31 '18 at 20:40
  • $\begingroup$ @GerhardPaseman fixed, and added explanation $\endgroup$ – user49822 Aug 31 '18 at 20:58
4
$\begingroup$

Quoting an answer I posted some time ago on MathSE:

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$. (N.B. The word "cycle" is used here in its group theory sense, not its graph theory sense!)

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 consisting of the black edges is self-complementary; the permutation $\alpha$ is an isomorphism between the black graph and the white graph.

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 bull graph.


An alternative proof is often given in graph theory textbooks, e.g., quoting Exercise 1.1.31 on p. 17 of Douglas B. West's Introduction to Graph Theory, second edition:

Prove that a self-complementary graph with $n$ vertices exists if and only if $n$ or $n-1$ is divisible by $4.$ (Hint: When $n$ is divisible by $4,$ generalize the structure of $P_4$ by splitting the vertices into four groups. For $n\equiv1$ mod $4,$ add one vertex to the graph constructed for $n-1.$)

$\endgroup$
  • $\begingroup$ Do all such finite complementary graphs arise this way? Gerhard "Not Fishing For More Complements" Paseman, 2018.08.31. $\endgroup$ – Gerhard Paseman Aug 31 '18 at 21:40
  • $\begingroup$ @GerhardPaseman Yes, of course. If $G=(V,E)$ is a self-complementary graph, let $\alpha\in\operatorname{Sym}(V)$ be an anti-automorphism of $G.$ $\endgroup$ – bof Aug 31 '18 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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