A graph which has the same number of edges as its complement must have number of vertices congruent to ________ or _____...

Question

A graph which has the same number of edges as its complement must have number of vertices congruent to ________ or ________ modulo 4.

Accepted Answer

n must be congruent to 0 or 1 modulo 4. G and its complement G-bar partition all C(n,2) edges of K_n. Equal edge counts require C(n,2) to be even, i.e., n(n-1)/4 must be an integer. Since n and n-1 are consecutive, 4 divides n(n-1) exactly when n = 0 mod 4 (so 4 divides n) or n = 1 mod 4 (so 4 divides n-1).