I need help with this graph proof please Let $G$ be a self-complementary graph in where $n = 4k+1$ . Prove that there is an odd number of vertices of degree $(n-1)/2$.
I dont even know where to start with this. I really need help.
Thanks!
 A: As it is isomorphic to its complement we can say that 
$$\sum_{i=1}^n deg(v_i)=\sum_{i=1}^n 4k-deg(v_i) $$ 
Then we have $$2\sum_{i=1}^n deg(v_i)=\sum_{i=1}^n 4k=4k(4k+1) $$
$$\sum_{i=1}^n deg(v_i)=2k(4k+1)$$
Notice that if $r=deg(v_i)$ then $4k-r$ is also a degree of another vertex. And if $r\neq 2k$ ,it is clear that it is another vertex. Set $s$ be number of vertex with degree $2k$ and $l$ be the number of vertex with degree less than $2k$. 
$$s2k+l(4k-r+r)=2k(4k+1)$$
$$s+2l=4k+1$$
$$s\equiv1 \text{ } mod(2)$$
A: Hint: $v$ has degree $\frac{n-1}{2}$ in $G$ if and only if $v$ has degree $\frac{n-1}{2}$ in its complement...
Can you  pair the vertices which don't have degree $\frac{n-1}{2}$?
A: If $E$ denotes the edge set of $G$ then $|E| = \frac{1}{2}\binom{|G|}{2}$ in a complementary graph (since the union of the edge sets of a graph and its complement gives the edge set of the complete graph on $|G|$ vertices).  THus, since $|G| = 4k+1$, you have $|E| = k(4k+1)$.  Furthermore, if a vertex has degree $m \leq \left\lfloor\frac{n-2}{2}\right\rfloor$ in the graph, it has degree $n-m-1$ in the complement of the graph (since each vertex has $n-1$ neighbours in the complete graph), so necessarily, we have a bijection between the set of vertices of degree $m$ and of degree $n-m-1$ in a self-complementary graph (when the degree is $(n-1)/2$, though, there is no such procedure of pairing elements as above).  Write $N_m$ to denote the number of vertices of degree $m$. Then we have (counting degrees overcounts edges twice over)
\begin{equation*}
2k(4k+1) = \sum_{v \in G} \deg(v) = 2kN_{(n-1)/2)} + 4k\sum_{m \leq (n-2)/2} N_m.
\end{equation*}
For $k \geq 1$, divide by $2k$ to get $4k+1 = N_{(n-1)/2} + 2\sum_{m \leq (n-2)/2}N_m$.  Reducing mod 2, we see that $N_{(n-1)/2}$ has to be odd.
