# Homework Help: Self Complementary Graph Proof

1. Mar 23, 2012

### Trentonx

1. The problem statement, all variables and given/known data
Suppose $G \cong\bar{G}$ and that $n = |V(G)|=4k+1$ for some $k \ge 1$. Suppose that the degree sequence of G is $d_{1}\ge d_{2} \ge ... \ge d_{n}$

Prove that $d_{i}+d_{n-i+1}=n-1$ for each $i=1, 2,...,n$

2. Relevant equations
I don't think there are any.

3. The attempt at a solution
I put the question in terms of k $d_{i}+d_{4k-i+2}=n-1$
and found the number of edges, since the graph has to have exactly half the maximum.
$|E(G)| = \frac{n(n-1)}{4}=\frac{(4k+1)(4k)}{4}=4k^{2}+4$
I'm not sure that help's, but I thought it might be useful. I need something about the degree sequence, and how it will look, but I'm not sure where to get that.