Re: on a self-complementary graph problem

Path	csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	alt.algebra.help, comp.programming
Subject	Re: on a self-complementary graph problem
Date	Sat, 16 Sep 2017 16:10:11 +0100
Organization	A noiseless patient Spider
Lines	118
Message-ID	<87mv5u8yss.fsf@bsb.me.uk> (permalink)
References	<86h8wbemis.fsf@toledo.com> <87zia3fxji.fsf@bsb.me.uk> <861sn6afyz.fsf@toledo.com>
Mime-Version	1.0
Content-Type	text/plain
Injection-Info	reader02.eternal-september.org; posting-host="baa04dd68ae3adbfd0da6a15d754bbba"; logging-data="8171"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+MuCKnmFdFPvln6rayL32mgiSty7qX5ZU="
Cancel-Lock	sha1:yMyWTZmhiK4JMWFLoXXjR+teO8c= sha1:ANV+DIt5CZJWZWpehJPSQv6QPzc=
Xref	csiph.com alt.algebra.help:4994 comp.programming:8007

Cross-posted to 2 groups.

Show key headers only | View raw

Daniel Bastos <dbastos@toledo.com> writes:

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

That's great.  It's just arithmetic now.  Take both sides mod 4:

  0 = v(v - 1) mod 4

Can you see what v mod 4 must be for v(v - 1) to be 0 mod 4?  If not,
here's how I'd show it (using rot13 and some spoiler alert lines)

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

V'q cebonoyl whfg yvfg gur pnfrf:

  i = 0 zbq 4 <=> i-1 = 3 zbq 4 <=> i(i-1) = 0 zbq 4
  i = 1 zbq 4 <=> i-1 = 0 zbq 4 <=> i(i-1) = 0 zbq 4
  i = 2 zbq 4 <=> i-1 = 1 zbq 4 <=> i(i-1) = 2 zbq 4
  i = 3 zbq 4 <=> i-1 = 2 zbq 4 <=> i(i-1) = 6 zbq 4 <=> 2 zbq 4

fb i(i - 1) = 0 zbq 4 vs naq bayl vs i = 0 zbq 4 be i = 1 zbq 4.

(Gurer'f cebonoyl fbzr avpr fvzcyr ehyr sbe fbyivat guvatf yvxr

  n = k(k - o) zbq a

ohg vg'f orra gbb ybat sbe zr!)

> Thanks!

You're welcome.  How nice to have a real question from a serious student.

-- 
Ben.

Thread

on a self-complementary graph problem Daniel Bastos <dbastos@toledo.com> - 2017-09-09 15:48 -0300
  Re: on a self-complementary graph problem Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-09 21:05 +0100
    Re: on a self-complementary graph problem Daniel Bastos <dbastos@toledo.com> - 2017-09-16 11:13 -0300
      Re: on a self-complementary graph problem Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-16 16:10 +0100
        Re: on a self-complementary graph problem Daniel Bastos <dbastos@toledo.com> - 2017-09-17 07:32 -0300

csiph-web