I need help with this graph proof please

Question

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!

Answer 1

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}$?

Answer 2

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.

Answer 3

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)$$