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
And, |E(G)|= m
It completment G' will have,
We require that,
|E(G)|=|E(G')| because the graphs are isomorphic.
We note that m is an integer.
4 divides n OR 4 divides (n-1) because gcd(n,n-1)
Thus, n=4k or n-1=4k ---> n=4k+1