From: cd@newsun-graphe.lri.fr (Charles Delorme)
Subject: Re: question about tournaments (graph theory)
Date: 29 Jun 2000 15:43:23 GMT
Newsgroups: sci.math
Summary: [missing]

In article <962234285.5073.0.nnrp-02.9e98127f@news.demon.co.uk>, "Felix Dilke" <fdilke@email.com> writes:
|> Does anybody have a quick answer to this little problem about tournaments (=
|> complete directed graphs):
|> 
|> Is there a (non-empty) tournament in which every edge belongs to at least 2
|> cyclic triangles?
|> 
|> Thanks in advance
|> 
|> Felix
|> 

Yes: consider the tournament on 7 vertices labeled 0,1,2...6,
with arcs (x-->x+1), (x-->x+2), (x-->x+4)
where the addition is performed modulo 7.

Then you notice that there are 7 automorphisms x|-->x+i ,i=0..6,
where the addition is performed modulo 7 and 3 automorphisms
x|-->2^k x, k=0..2, where the multiplication  is performed modulo 7.

Fiddling with these automorphisms, you can find an automorphism
that sends the arc (0-->1) to any arc of the tournament.

And then you notice the two cyclic triangles
that contain that arc, namely 0-->1-->3-->0 and 0-->1-->5-->0.


-- 
Charles Delorme  tous les mégalomanes
LRI              ont une signature
cd@lri.fr        à étages