Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #8003 > unrolled thread

on a self-complementary graph problem

Back to article view | Back to comp.programming

Contents

  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

#8003 — on a self-complementary graph problem

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

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.

Thank you.

[toc] | [next] | [standalone]

#8004

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.

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.

[toc] | [prev] | [next] | [standalone]

#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!

[toc] | [prev] | [next] | [standalone]

#8007

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.

[toc] | [prev] | [next] | [standalone]

#8009

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

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

I can.  The integers modulo 4 are 0, 1, 2, 3.  The only ones that can
satisfy the equation are 0 and 1 --- as you showed below.

> If not, here's how I'd show it (using rot13 and some spoiler alert
> lines)

How nice to see someone using rot13! :-)

> I'd probably just list the cases:
>
>   v = 0 mod 4 <=> v-1 = 3 mod 4 <=> v(v-1) = 0 mod 4
>   v = 1 mod 4 <=> v-1 = 0 mod 4 <=> v(v-1) = 0 mod 4
>   v = 2 mod 4 <=> v-1 = 1 mod 4 <=> v(v-1) = 2 mod 4
>   v = 3 mod 4 <=> v-1 = 2 mod 4 <=> v(v-1) = 6 mod 4 <=> 2 mod 4
>
> so v(v - 1) = 0 mod 4 if and only if v = 0 mod 4 or v = 1 mod 4.
>
> (There's probably some nice simple rule for solving things like
>
>   a = x(x - b) mod n

[...]

I wonder that myself.  I think what we want here is to claim we have an
integral domain, an algebraic structure to the effect that a product 
xy = 0 if both x, y are zero.  Had we this structure, we'd be looking
for solutions of

      v = 0 mod 4
  v - 1 = 0 mod 4

But I think the structure here is Z/4Z, a quotient ring.  Since 4 is not
prime, there are factors x, y such that 4 = xy.  Since 4 = 0 mod 4, it
turns out that x = 2, y = 2 satisfy 4 = xy = 0, but both x,y are
nonzero.  Therefore Z/4Z is not an integral domain and so the argument
laid out doesn't apply here.

Nevertheless, since you listed out all cases, I think that proves it.

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

How nice to have someone to investigate these matters with!  Thank you!

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web