self-complementary graph: Number of Edges

Question

I know the number of edges for a self-complementary graph is $\frac{n(n-1)}{4}$, but how do I derive this?

Answer 1

The number of edges in a complete graph on n vertices $|E(K_{n})|$ is $^{n}C_{2}=\frac{n(n-1)}{2}$.

If a graph $G$ is self complementary we can set up a bijection between its edges, $E$ and the edges in its complement, $E'$. Hence $|E|=|E'|$.

Since the union of edges in a graph with those of its complement form the edges of a complete graph $K_{n}$ we have $|E|+|E'|=|E(K_{n})|$.

Since $|E|=|E'|$ we have $2|E|=\frac{n(n-1)}{2}$ and dividing by 2 completes the proof i.e. $|E|=\frac{n(n-1)}{4}$.

Answer 2

Let $G$ be a graph with $n$ verticies. The complete graph has $n(n-1)/2$ edges. If $G$ has $k$ edges then it's complement will have $n(n-1)/2-k$ edges. These number of edges will need to be equal if the $G$ is self complmentary so ....

Answer 3

First of all, for two graphs to be isomorphic, they need to have same number of edges (necessary condition).

Now, let $G(V,E)$ be a graph and $\overline{G}(\overline{V},\overline{E})$ be $G$'s compelement. Then if we unite these two graphs (I'm not sure whether $G \cup \overline{G}$ is the correct notation), what we get is a complete graph $K_n$. We know that $K_n$ has $\frac{n(n-1)}{2}$ edges. And we also know that $|E| = |\overline{E}|$. So $$|E|+|\overline{E}| = \frac{n(n-1)}{2} \implies |E| = |\overline{E}| = \frac{n(n-1)}{4}$$