I tried to prove this by induction.
Base case $n=1$, $5$ vertices. I just drew a pentagon, which has $5$ vertices of degree $2$
Then I assume for $n=k$,$4k+1$ vertices, there is at least one vertex with degree $2n$. The number of edges for this graph is $\dfrac{(4k+1)(4k)}{4}=(4k+1)(k)$
Then for $n=k+1$,$4k+5$ vertices. The number of edges is $\dfrac{(4k+5)(4k+4)}{4}=(4k+5)(k+1)$
The graph with $4k+1$ vertices have $8k+5$ more edges than the graph with $4k$ vertices.
This is where I get stuck.Am I on the right track? How should I proceed from here?
Best Answer
The complementary graph to $G$ adds all edges that are missing from the complete graph $K_{4n+1}$, and removes all existing edges. In $K_{4n+1}$ every vertex has $4n$ edges, so the complementing process changes each vertex degree from $x$ to $4n-x$.
The self-complementary graph must have the same degree sequence as its complement, and each vertex has its degree change from $\text{deg}(v)$ to $4n{-}\text{deg}(v)$ in the switch to the complement - so there must also be a vertex of that degree in the original graph to switch back. This corresponds to switching between an early position in the degree sequence and a late one.
So at the middle position $2n{+}1$ in the degree sequence, we must have a vertex that switches value with itself; that is, $\text{deg}(v) = 4n{-}\text{deg}(v)$. Which means for at least that vertex, $\text{deg}(v) = 2n$.
As an aside, you might also like to consider the other $5$-vertex self-complementary graph (apart from the $5$-cycle) in any proof you attempt: (from http://mathworld.wolfram.com/Self-ComplementaryGraph.html):
Here $n=1$ of course and the middle position of the degree sequence is $3$ - and we see the sequence of $(3,3,\color{red}{2},1,1)$.