[Math] Show that if $G$ is a simple, regular self-complementary graph with $n$ vertices, then $n ≡ 1 (mod 4)$

graph theory

Problem: Show that if G is a simple, regular self-complementary graph with $n$ vertices, then
$n ≡ 1 (mod 4).$

Thoughts: Suppose $G$ is self complementary. Then $|E(G)|+|E(G_{complement})|=$ $n \choose 2$, hence
$|E(G)| = \frac {(n)(n-1)}{4}$ so that $|E(G)|$ (an integer) yields remainder $0$ or $1$ divided by $4$. How can I show that because the graph is regular that it will not be divisible by $4$?

Best Answer

Hint Since the graph is $d$ regular, so is its complement. Therefore $$n-1=\deg_G(v) + \deg_{\bar{G}}(v)=2d$$

Related Question