MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
0

If ${n \choose 2}$ is even, does there exist a self-complementary graph on $n$ vertices?

flag
3 
 See: math.stackexchange.com/q/40745 – Theo Buehler Dec 8 2011 at 7:09
Yes. In fact there are lots for $n$ large and congruent to 0 or 1 (mod 4). See oeis.org/A000171 – Tony Huynh Dec 8 2011 at 7:17
I wonder if for large enough $n$ the existence would follow by a probabilistic argument. – Dima Pasechnik Dec 8 2011 at 11:08
As per the faq, this website is for questions of interest to mathematical researchers, not for questions of the type one sees in the exercises of intro undergrad textbooks. No harm done - others have pointed you in the right direction. – Gerry Myerson Dec 8 2011 at 11:51
That's a very nice algorithm. Thanks, Theo! Thanks, Tony! Maybe so, Dima. By Tony's link there are a lot of them, and so presumably there are many which satisfy a stronger, more identifiable self-complimentary property. Which would make a probabilistic argument easier. I'll have to think about it. – Jay Cummings Dec 9 2011 at 2:00

closed as off topic by Gjergji Zaimi, Gerry Myerson, Qiaochu Yuan, Igor Rivin, Tony Huynh Dec 8 2011 at 13:56

Browse other questions tagged or ask your own question.