Thread: self-complementary graph

A simple graph G is self-complimentary. Show there exists an integer k such that the order of G = 4k or 4k+1.

I'm feeling a tad lost on this. I understand the idea of self-complimentary. G and its compliment will be isomorphic and have the same deg sequence, order, size.
I have a feeling that the relation between the compliment, G and a complete graph will come in handy ie) the compliment of G= k -E(G) where k here should have subscript n for complete graph, this is a different k than in the question.

Any thoughts on this would be appreciated.

Originally Posted by jaidon

A simple graph G is self-complimentary. Show there exists an integer k such that the order of G = 4k or 4k+1.

I'm feeling a tad lost on this. I understand the idea of self-complimentary. G and its compliment will be isomorphic and have the same deg sequence, order, size.
I have a feeling that the relation between the compliment, G and a complete graph will come in handy ie) the compliment of G= k -E(G) where k here should have subscript n for complete graph, this is a different k than in the question.

Any thoughts on this would be appreciated.

Let n>1.
Let |V(G)|=n.
And, |E(G)|= m

It completment G' will have,
|V(G')|=n
And, |E(G)|=n(n-1)/2-m

We require that,
|E(G)|=|E(G')| because the graphs are isomorphic.
Thus,
n(n-1)/2-m=m
Thus,
n(n-1)/2=2m
Thus,
n(n-1)/4=m

We note that m is an integer.
Thus,
4 divides n OR 4 divides (n-1) because gcd(n,n-1)
Thus, n=4k or n-1=4k ---> n=4k+1