Question
Prove that for every integer k≥1, exists a self-complementary graph with 4k vertices half of which are of degree 2k-1 and the other half of degree 2k.
My approach
So, I think the easiest way to prove what is asked is by induction. I can prove the base case for k=1, but as far as the inductive step is concerned, I cannot seem to reach a conclusion as to why if the statement holds for n, then it holds for n+1.
Any help would be appreciated.
Here is a simple direct construction of a self-complementary graph $G$ on $4k$ vertices where all vertices have degree $2k$ or $2k-1$.
$V(G)=A\cup B\cup C\cup D$ where $A,B,C,D$ are disjoint $k$-element sets. $$a\in A\implies N(a)=(A\setminus\{a\})\cup B.$$ $$b\in B\implies N(b)=A\cup C.$$ $$c\in C\implies N(c)=B\cup D.$$ $$d\in D\implies N(d)=C\cup(D\setminus\{d\}).$$
Let $\varphi:V(G)\to V(G)$ be a bijection such that $\varphi(A)=B$, $\varphi(B)=D$, $\varphi(C)=A$, and $\varphi(D)=C$; then $\varphi$ is an anti-automorphism of $G$, showing that $G$ is self-complementary.
A vertex $v$ has degree $2k$ if $v\in B\cup C$, degree $2k-1$ if $v\in A\cup D$.