Path: csiph.com!aioe.org!.POSTED!not-for-mail From: Daniel Bastos Newsgroups: alt.algebra.help,comp.programming Subject: Re: on a self-complementary graph problem Date: Sun, 17 Sep 2017 07:32:35 -0300 Organization: Aioe.org NNTP Server Lines: 102 Message-ID: <86zi9t7gzg.fsf@toledo.com> References: <86h8wbemis.fsf@toledo.com> <87zia3fxji.fsf@bsb.me.uk> <861sn6afyz.fsf@toledo.com> <87mv5u8yss.fsf@bsb.me.uk> NNTP-Posting-Host: czbaxA2UCA/sefhlz0UzmQ.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:J7mcDxmSmWUEiIqP+3K3S3P6910= X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com alt.algebra.help:4996 comp.programming:8009 Ben Bacarisse writes: > Daniel Bastos writes: > >> Ben Bacarisse writes: >> >>> 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. >> >> 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!