Path: csiph.com!aioe.org!.POSTED!not-for-mail
From: Daniel Bastos <dbastos@toledo.com>
Newsgroups: alt.algebra.help,comp.programming
Subject: Re: on a self-complementary graph problem
Date: Sat, 16 Sep 2017 11:13:56 -0300
Organization: Aioe.org NNTP Server
Lines: 63
Message-ID: <861sn6afyz.fsf@toledo.com>
References: <86h8wbemis.fsf@toledo.com> <87zia3fxji.fsf@bsb.me.uk>
NNTP-Posting-Host: BA7GfgzDJAJU6NkcC5s5CQ.user.gioia.aioe.org
Mime-Version: 1.0
Content-Type: text/plain
X-Complaints-To: abuse@aioe.org
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt)
Cancel-Lock: sha1:RP+T7UVhHJq3IY+OIrdqT29pgwg=
X-Notice: Filtered by postfilter v. 0.8.2
Xref: csiph.com alt.algebra.help:4992 comp.programming:8005

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Daniel Bastos <dbastos@toledo.com> 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.

By definition, e(G^c) = e(K_n) - e(G).  I know e(G) and e(G^c) have the
same number of vertices and edges because G =~ G^c.  Also, from exercise
1.1.3, I know

   e(G^c) <= (v 2)
   e(G)   <= (v 2)

By exercise 1.2.7, I know 

   e(K_n) = (v 2)

Combining the definition of G^c with these facts, I get    

  e(G^c) + e(G) = (v 2) = 1/2 v (v - 1).

(*) Attempt 1

Let G be self-complementary.  I must show v = 0 or 1 mod 4. 

Let e := e(G) = e(G^c).  Then from

  e(G^c) + e(G) = (v 2) = 1/2 v (v - 1) 

we get 

  2e = 1/2 v (v - 1)

implying

  4e = v (v - 1)

Which numbers v satisfy this equation?  I can't honestly deduce the
result here.  At least not at the moment.

> Does that help?

It sure did.  When I started I couldn't deduce anything.

>> 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.

Thanks!