Prove that ∀k∈N, k≥1, there is a self-complementary graph with 4k+1 vertices, which is 2k-regular.
I think that the best way to prove it is by induction.
Any helpful suggestions?
(I know that this post: "Prove every self-complementary graph with 4n+1 vertices has at least one vertex of degree 2n" exists and I do not think that I am asking the same question. However, if you disagree with me I am willing to remove my post.)
Here is a neat construction that works when $n = 4k+1$ is a prime.
We think of the vertices as belonging to the group $\mathbb{Z}_n$ of integers mod $n$. We connect two vertices $x,y$ if $x-y$ is a non-zero quadratic residue. Since $n \equiv 1 \pmod{4}$, $-1$ is a quadratic residue, and so this is well-defined ($x-y$ is a non-zero quadratic residue iff $y-x$ is). In the complement graph, two vertices $x,y$ are connected if $x-y$ is a quadratic non-residue.
To show that the graph is isomorphic to its complement, take any quadratic non-residue $a$, and map $x$ to $ax$. Since $a$ is a quadratic non-residue, if $x \neq y$ then $x-y$ is a quadratic residue iff $a(x-y)$ is a quadratic non-residue.
As an example, when $n = 5$, the vertices are $0,1,2,3,4$, and we simply get the pentagon $(0,1),(1,2),(2,3),(3,4),(0,4)$, since the quadratic residues are $1,4$.