We are now ready to prove the main result whose statement follows.

We prove necessity by induction on *n*. Let *X* be a self-complementary
circulant graph of smallest order which is a counter-example. We know that
is satisfied. Hence, *n* is composite and has
2*r*, *r*>0, primes congruent to 3 modulo 4 in its prime factorization.

Since *n* is composite and *X* is self-complementary,
and
implying that Aut(*X*) is imprimitive by Theorem 1.9.
Suppose the blocks have length *d* and
.
By Lemma 1.8 we know that the blocks
have the form
,
.
Since *X*^{c} has the same
automorphism group as *X*,
are also the blocks
of length *d* for
the group acting on *V*(*X*^{c}). Thus, any isomorphism of *X* to
*X*^{c} must act as a permutation on the set of blocks. The action
of
tells us that the subgraphs
induced
by *X* on
,
respectively, are all isomorphic
to each other. Further, the action of
implies that
are all circulant graphs. We conclude that *X*_{0}itself is a self-complementary circulant graph.

The permutation
cyclically permutes the blocks so that the action
of
on the blocks contains the regular
representation of the
cyclic group of order *n*/*d*. If
is imprimitive, then
we can find a block system for Aut(*X*) acting on *V*(*X*) with blocks of
length *d*', where *d*'>*d*, by Proposition 1.10. Without loss of generality,
we may assume that
are maximal non-trivial blocks
of Aut(*X*), that is, the only block properly containing *B*_{0} is all of
*V*(*X*).

Since *X* is a minimal counter-example, the self-complementary circulant
subgraph *X*_{0} cannot be a counter-example. Thus, the prime factorization
of *d* has no primes congruent to 3 modulo 4. However, *n* has at least
two primes congruent to 3 modulo 4 in its prime factorization. Thus,
*n*/*d* is composite and
is either doubly
transitive or
imprimitive. It cannot be imprimitive as this would allow us to find
a non-trivial block properly containing *B*_{0}. Hence,
acts doubly transitively on the set of blocks. This implies that the
number of edges between any two blocks is the same. However, there are
*d*^{2} possible edges between any two blocks which is odd because *d* is odd.
This means that the parities of the numbers of edges between any two
blocks in *X* and *X*^{c} are different. Thus, *X* cannot be
self-complementary. The necessity now follows.