I know the number of edges for a self-complementary graph is $\frac{n(n-1)}{4}$, but how do I derive this?
[Math] self-complementary graph: Number of Edges
combinatoricsgraph theory
Related Solutions
Hint:
Given a self complementary graph on $n$ vertices, try to construct a self-complementary graph on $n+4$ vertices.
Elaboration on the hint:
Given a self-complementary graph $G$ with $n$ vertices, add 4 more vertices which already form a 'Z' graph (the self-complementary graph for $n=4$). Connect the vertices of $G$ to some of four newly added vertices. Show that the new graph so formed, is a self-complementary graph on $n+4$ vertices.
Full answer:
Connect every vertex of $G$ to two of the vertices which are the farthest apart on the the n=4 graph (which is basically a path, and you connect all vertices of $G$ to the end points of that path).
This works even when $G$ has only one vertex.
For any $n\in\mathbb N,$ here's how you can construct a self-complementary graph of diameter $2$ and order $4n+1.$
Choose a graph $G$ of order $n.$
Start with a $C_5$ graph, with vertices $A,B,C,D,E$ and edges $AB,BC,CD,DE,EA.$
Replace each of the vertices $B$ and $E$ with a copy of $G,$ and replace each of the vertices $C$ and $D$ with a copy of the complementary graph $\overline G.$
More precisely: The graph has vertex set $A\cup B\cup C\cup D\cup E$ where $A,B,C,D,E$ are disjoint sets and $|A|=1$ and $|B|=|C|=|D|=|E|=n.$ The induced subgraphs on $B$ and $E$ are isomorphic to $G,$ the induced subgraphs on $C$ and $D$ are isomorphic to $\overline G.$ There are edges joining all vertices in $A$ to all vertices in $B,$ all vertices in $B$ to all vertices in $C,$ all vertices in $C$ to all vertices in $D,$ all vertices in $D$ to all vertices in $E,$ and all vertices in $E$ to all vertices in $A.$ On the other hand, there are no edges between $A$ and $C,$ or between $C$ and $E,$ or between $E$ and $B,$ or between $B$ and $D,$ or between $D$ and $A.$
In other words: Just use the most obvious construction of a self-complementary graph of order $4n+1.$
Example: For $G=K_2$ it looks like
Best Answer
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}$.