Path: csiph.com!aioe.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: alt.algebra.help,comp.programming Subject: Re: on a self-complementary graph problem Date: Sat, 09 Sep 2017 21:05:05 +0100 Organization: Aioe.org NNTP Server Lines: 26 Message-ID: <87zia3fxji.fsf@bsb.me.uk> References: <86h8wbemis.fsf@toledo.com> NNTP-Posting-Host: wz2xIpMgzcNFB6/TmMn2fg.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain X-Complaints-To: abuse@aioe.org X-Notice: Filtered by postfilter v. 0.8.2 Cancel-Lock: sha1:MysgPmxy2HRg3961V+zsfh39fOo= Xref: csiph.com alt.algebra.help:4990 comp.programming:8004 Daniel Bastos writes: > I'm looking for a strategy on how to solve this problem. I appreciate > any direction you may give me. > > Problem. A simple graph G is self-complementary if G =~ G^c. Show if G > is self-complementary, then v = 0 (mod 4) or v = 1 (mod 4). Let's say G has n vertices. G^c is K_n with the edges of G removed. What do you know about e(G) and e(G^c)? What does that tell you about e(K_n)? Now consider exercise 1.2.7. Does that help? > This is problem 1.2.11 item (b) in ``Graph theory with applications'' by > J.A. Bondy and U.S.R. Murty, Department of Combinatorics and > Optimization, University of Waterloo, Ontario, Canada. North-Holland, > fifth printing, 1982. ISBN: 0-444-19451-7. The book uses K_n for the complete simple graph with n vertices. Exercise 1.2.7 is to show that e(G) = (v 2) if and only if G is complete (here I'm writing (v 2) for the binomial coefficient). =~ is graph isomorphism. -- Ben.