## prizzyjade one year ago A simple graph that is isomorphic to its complement is self complementary. a. Prove that if G is self complementary, then G has 4k or 4k+1 vertices where k is an integer.

1. zzr0ck3r

The statement should include $$4k$$ not just$$4k+1$$ (look at part b) The complete graph with $$n$$ vertices has $$\frac{1}{2}n(n-1)$$ edges. Why? Because for each of the $$n$$ vertices, there is $$n-1$$ edges, but we count them all twice. If a graph is self complimentary there must be $$\frac{1}{2}(\frac{1}{2}n(n-1))$$ edges because the compliment must have equal amount of edges. Now if $$\frac{1}{4}n(n-1)\in \mathbb{Z}$$ then it must be that $$4$$ divides $$n(n-1)$$. In other words $$n=4k$$ or $$n=4k+1$$

2. zzr0ck3r

b) there is one self complimentary graph on 4 verts. Hint: it is super easy and I must draw the LINE at how much i will give.

3. zzr0ck3r

For 5 verts. I am sure that if you CYCLE through all the graphs you have in your wheel HOUSE I bet you will find it.

4. zzr0ck3r

Im Sorry.for not replying I still have class sorry

6. zzr0ck3r

no problem. Class is important :)

thanks for the help ....

I'm having a hard time analyzing the problems coz i cant focus having so many math subjects ..

9. zzr0ck3r

what all are you taking?

Calculus with analytic geometry ,physics(i know its science but still it uses math ) and graph theory...

11. zzr0ck3r

yep, that is a full boat